匹配最长公共前缀

我采用的方法为相对比较暴力的,但是也是较容易理解得,废话少说上代码:

class Solution {
    public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
        return "";
    }

    // 最长前缀末尾位置
    int end = strs[0].length() - 1;

    for (int i = 1; i < strs.length; ++i) {
        int j = 0;
        // 优化1: 不用比较整个字符串, 只要比较前缀长度即可
        for (; j <= end && j < strs[i].length(); ++j) {
            if (strs[0].charAt(j) != strs[i].charAt(j)) {
                break;
            }
        }
        // j 的位置不相同
        end = Math.min(end, j - 1);

        // 没有公共前缀, 不用再遍历剩余字符串
        if (end < 0) break;
    }

    return strs[0].substring(0, end + 1);
}
}

因为我们在传入多个字符串进行判定的时候,从前往后比较过程中,最长公共前缀肯定是越来越短的,所以我们把第一个子串作为对比子串,其他的为比较子串。

上一篇:阿里巴巴校招笔试题10.8


下一篇:474. 一和零