Longest Common Prefix

The Longest Common Prefix algorithm identifies the longest string that is a prefix of every string in an input array. This is a fundamental string operation useful in scenarios like autocomplete suggestions or file path analysis.

How it Works

The algorithm operates by iterating through the characters of the first string, using it as a reference. For each character, it checks if the same character exists at the identical position in all other strings. This process continues until a mismatch is found or the end of one of the strings is reached.

1. Initialize with the First String: The algorithm starts by assuming the first string in the array holds the potential longest common prefix. It then iterates character by character through this first string. 2. Vertical Comparison: For each character at a given index `i` from the first string, it performs a vertical scan. It compares this character against the character at index `i` in *every other* string in the array. 3. Detecting Mismatch or End of String: If, during this vertical scan, any string is shorter than the current index `i`, or if its character at index `i` does not match the reference character from the first string, a mismatch is detected. 4. Returning the Prefix: Upon detecting a mismatch, the algorithm immediately stops. The longest common prefix found so far is the substring of the first string from its beginning up to the index `i` where the mismatch occurred. 5. Full Match: If the algorithm completes iterating through the entire first string without any mismatches, then the first string itself is the longest common prefix.

function longestCommonPrefix(strs):
    if strs is empty: return ""

    for i from 0 to length(strs[0]) - 1:
        char = strs[0][i]
        for each string s in strs:
            if i >= length(s) or s[i] != char:
                return strs[0] up to index i (exclusive)

    return strs[0]

Key Takeaways

• The algorithm uses the first string as a reference for comparison.
• It performs character-by-character vertical comparisons across all strings.
• It stops immediately upon finding the first character mismatch or end of a string.
• The efficiency comes from early exit, avoiding unnecessary comparisons.