14 Longest Common Prefix – Easy¶

Problem:¶

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

Thoughts:¶

Get the first string in the array of strings, the longest common prefix is at best this first string.

So iterate over all strings, and find out if there is a common prefix for the current string and current prefix.

If the first string length is m, and there are n strings. This method will be O(mn) running time.

There could be a optimized solution. Instead of always start with the first string in the array, init the prefix to be the shortest string in the array. If k is the shortest string’s length, then running time would be O(kn). This is helpful when k is significantly smaller than m, where m is the first string length.

Solutions:¶

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i ++ ) {
            for (int j = 0; j < prefix.length(); j ++){
                if (j == strs[i].length() || prefix.charAt(j) != strs[i].charAt(j)) {
                    prefix = prefix.substring(0, j);
                    break;
                }
            }
        }
        return prefix;
    }
}