14. Longest Common Prefix

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



Solution:

Method 1:

We set the entire string of the first input to be prefix.

Go through the string array, check if the current string has such prefix. If not, decrease the length of prefix and try again.

After going through the string array, the prefix left is the largest common prefix we are looking for.



Code:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String pre = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(pre) != 0) {
                pre = pre.substring(0, pre.length() - 1);
            }
        }
        return pre;
    }
}

Method 2: sort

We sort the string array first. Then check the first and last string. The prefix of these two is the longest one we are looking for.



Code:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Arrays.sort(strs);
        String first = strs[0];
        String last = strs[strs.length - 1];
        for (int i = 0; i < first.length(); i++) {
            if (i < last.length() && first.charAt(i) == last.charAt(i)) {
                sb.append(first.charAt(i));
            }
            else {
                break;
            }
        }
        return sb.toString();
    }
}