Longest Common Prefix

Problem Statement

LeetCode-14: 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 “”.

Consider the following example:

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

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There isn't any common prefix among the input strings.

Approach

As the prefix will have to be one of the input string, let’s consider the first string as the prefix. We will iterate over the rest of the strings and keep updating the prefix by comparing it with the current string.

In every iteration, we will compare the prefix with the curr string. If the current string does not start with the prefix, we will keep removing the last character from the prefix and try again.

We will continue this process until the prefix is a substring of the current string or the prefix becomes empty. Consider the following example for input: ["flower","flow","flight"]:

prefix: "flower"
curr: "flow"

evaluate: "flow".indexOf("flower") != 0
prefix: "flowe"

evaluate: "flow".indexOf("flowe") != 0
prefix: "flow"

evaluate: "flow".indexOf("flow") == 0
prefix: "flow"

Implementation

Here is the implementation of the above approach:

public String longestCommonPrefix(String[] strs) {
    String prefix = strs[0];

    for (String curr : strs) {
        while (curr.indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
        }
        
        if(prefix.length() == 0){
            break;
        }
    }
    return prefix;
}

Complexity Analysis

The time complexity for this approach is $O(S)$, where $S$ is the sum of lengths of all characters in the input strings. The space complexity is $O(1)$.

Follow-up

Another approach is to sort the input strings and then compare the first and last string to find the longest common prefix.

This approach works because the first and last strings will have the maximum difference in characters. So, the common prefix will be the longest common prefix among all the strings.

public String longestCommonPrefix(String[] strs) {
    Arrays.sort(strs);
    
    String firstString = strs[0];
    String lastString = strs[strs.length -1];
    int index = 0;

    while(index < firstString.length() && index < lastString.length()){
        if(firstString.charAt(index) == lastString.charAt(index)){
            index++;
        }else{
            break;
        }
    }

    return firstString.substring(0, index);
}

This approach has a time complexity of $O(n \cdot \log n + M)$, where $n$ is the number of input strings and $M$ is the length of first and last strings.

PS: The problem is a typical use-case of the Trie data structure. We can build a Trie of all the input strings and then traverse the Trie to find the longest common prefix.