Longest Common Prefix easy

Problem Statement

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 "".

Example 1

Input: strs = ["flower","flow","flight"] Output: "fl"

Example 2

Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

Steps

1. Handle Edge Cases: Check for empty input array. If empty, return "". If the array contains only one string, return that string.

2. Iterate through the shortest string: Find the shortest string in the array. We only need to compare up to the length of the shortest string because a longer prefix can't be common to all.

3. Character-by-Character Comparison: Iterate through the characters of the shortest string. In each iteration, compare the current character with the corresponding character in all other strings.

4. Prefix Construction: If a character matches in all strings, add it to the prefix string. If a mismatch is found, stop the iteration and return the current prefix.

5. Return the Prefix: After iterating through the shortest string, return the constructed prefix.

Explanation

The algorithm leverages the fact that the longest common prefix cannot be longer than the shortest string in the array. By iterating character by character through the shortest string and comparing each character across all strings, we efficiently find the longest common prefix. The algorithm stops as soon as a mismatch is detected, optimizing for cases where no common prefix exists.

Code (TypeScript)

function longestCommonPrefix(strs: string[]): string {
    if (strs.length === 0) return ""; // Handle empty array
    if (strs.length === 1) return strs[0]; // Handle single string

    let shortestStr = strs.reduce((a, b) => a.length <= b.length ? a : b); //Find the shortest string
    let prefix = "";

    for (let i = 0; i < shortestStr.length; i++) {
        const char = shortestStr[i];
        let match = true;
        for (let j = 0; j < strs.length; j++) {
            if (strs[j][i] !== char) {
                match = false;
                break;
            }
        }
        if (match) {
            prefix += char;
        } else {
            break; // Mismatch found, stop iteration
        }
    }

    return prefix;
}

Complexity

• Time Complexity: O(S * N), where N is the number of strings and S is the length of the shortest string. In the worst case, we iterate through all characters of the shortest string and compare each character with all other strings.

• Space Complexity: O(1). We only use a few variables to store the prefix and intermediate values; the space used doesn't depend on the input size. The space used by prefix is at most the length of the shortest string.