Tuesday, July 22, 2014

Longest Common Prefix

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

比较直观,两两比较,更新prefix,当prefix已经为""时,可以直接结束。
public class Solution {
    //Time: O(n * average length of each String)
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            while (j < prefix.length() && j < strs[i].length()) {
                if (prefix.charAt(j) != strs[i].charAt(j)) {
                    break;
                }
                j++;
            }
            prefix = prefix.substring(0, j);
            if (prefix == "") {
                return "";
            }
        }
        return prefix;
    }
}

No comments:

Post a Comment