[LeetCode] 14. Longest Common Pr

</br>

Write a function to find the longest common prefix string amongst an array of strings.

</br>

Solution

The most straightforward way to this problem is to individually compare the longest common prefix with string[i], and update the common prefix when the current one does not match the string[i].

However, this method has to iterate all characters in every strings, so if there is a very short string in the back of the array, the algorithm still has to iterate all possible scenarios.

Hence, we can compare the same position of characters of each string first and then move to the next position. In this way, when we reach the length of the shortest string, the algorithm will stop.

Java

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) 
        return "";

    for (int i = 0; i < strs[0].length() ; i++){
        //we only have to choose character from the first string
        char target = strs[0].charAt(i);
        //compare this character to the same position of each string
        for (int j = 1; j < strs.length; j ++) {
            if (i == strs[j].length() || strs[j].charAt(i) != target)
                return strs[0].substring(0, i);             
        }
    }
    return strs[0];
}

</br>