Leetcode Day 4: Longest Common Prefix Explained

simona-cancian

Simona Cancian

Posted on July 5, 2024

Leetcode Day 4: Longest Common Prefix Explained

The problem is as follows:
Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Here is how I solved it:

  • If there input list of strings is empty, it means that there is no common prefix to check so we return an empty string.
if not strs:
    return ""
Enter fullscreen mode Exit fullscreen mode
  • Use the first string in the list as a reference for comparison
for i in range(len(strs[0])):
    char = strs[0][i]
Enter fullscreen mode Exit fullscreen mode
  • For each character in the reference string, compare it with the corresponding character in all other strings. If any string has a different character at the same position or is shorter than current position i, it means that the common prefix ends before this character. Therefore, return the substring of the reference string up to this point.
for string in strs[1:]:
    if i >= len(string) or string[i] != char:
        return strs[0][:i]
Enter fullscreen mode Exit fullscreen mode
  • If loops completes without returning, it means that the reference string itself is the longest common prefix
    return strs[0]
Enter fullscreen mode Exit fullscreen mode

OR just use os standard library available in Python. It includes functions for file and directory manipulation, environment variables, process management etc.
The os module provides a way to interact with the operating system in a portable way.
Here is the completed solution:

import os

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = os.path.commonprefix(strs)
        return prefix
Enter fullscreen mode Exit fullscreen mode
💖 💪 🙅 🚩
simona-cancian
Simona Cancian

Posted on July 5, 2024

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related