Longest Common Prefix

Difficulty: Easy | Acceptance: 46.02% | Paid: No

Topics: Array, String, Trie

• Examples
• Constraints
• Brute Force - Vertical Scanning
• Optimal - Horizontal Scanning
• Divide and Conquer

Examples

Input

strs = ["flower","flow","flight"]

Output

"fl"

Input

strs = ["dog","racecar","car"]

Output

""

Explanation

There is no common prefix among the input strings.

Constraints

- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] consists of only lowercase English letters.

Brute Force - Vertical Scanning

Intuition

We can scan the strings vertically, character by character, checking if all strings have the same character at each position until a mismatch is found.

Steps

• Iterate through the characters of the first string.
• For each character index, compare it with the character at the same index in all other strings.
• If a mismatch is found or if we reach the end of any string, return the prefix up to that point.

def longestCommonPrefix(strs):
    if not strs:
        return ""
    prefix = ""
    for i in range(len(strs[0])):
        char = strs[0][i]
        for j in range(1, len(strs)):
            if i >= len(strs[j]) or strs[j][i] != char:
                return prefix
        prefix += char
    return prefix

Complexity

• Time: O(S) where S is the sum of all characters in all strings.
• Space: O(1) as we only use a constant amount of extra space.

Optimal - Horizontal Scanning

Intuition

Compare the prefix of the first two strings, then compare that prefix with the next string, and so on, reducing the prefix length at each step.

Steps

• Initialize the prefix as the first string.
• Iterate through the rest of the strings.
• For each string, find the common prefix between the current prefix and the string.
• Update the prefix accordingly. If at any point the prefix becomes empty, return it immediately.

def longestCommonPrefix(strs):
    if not strs:
        return ""
    prefix = strs[0]
    for i in range(1, len(strs)):
        while not strs[i].startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

Complexity

• Time: O(S) where S is the sum of all characters in all strings.
• Space: O(1) as we only use a constant amount of extra space.

Divide and Conquer

Intuition

Recursively divide the array of strings into two halves, find the common prefix for each half, and then find the common prefix of the two prefixes.

Steps

• If the array contains only one string, return that string as the prefix.
• Divide the array into two halves.
• Recursively find the common prefix for each half.
• Find the common prefix of the two prefixes obtained from the previous step.

def longestCommonPrefix(strs):
    if not strs:
        return ""
    return longestCommonPrefixHelper(strs, 0, len(strs) - 1)

def longestCommonPrefixHelper(strs, left, right):
    if left == right:
        return strs[left]
    mid = (left + right) // 2
    lcp_left = longestCommonPrefixHelper(strs, left, mid)
    lcp_right = longestCommonPrefixHelper(strs, mid + 1, right)
    return commonPrefix(lcp_left, lcp_right)

def commonPrefix(str1, str2):
    min_len = min(len(str1), len(str2))
    for i in range(min_len):
        if str1[i] != str2[i]:
            return str1[:i]
    return str1[:min_len]

Complexity

• Time: O(S) where S is the sum of all characters in all strings.
• Space: O(m * log n) where m is the length of the longest string and n is the number of strings. This accounts for the recursion stack.