Leetcode 14. Longest Common Prefix

题目描述:找各个字符串最长前缀,返回。

题目链接:Leetcode 14. Longest Common Prefix

构建一个字典树,然后遍历到某个点下有多个孩子,则该点为最长前缀。
但是建树的开销就很大了,再加上遍历查找的话更大,倒不如随便选一个word然后逐位比较直至没有共同点位置。

代码如下


class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length <= 1) {
            return strs.length == 0 ? "" : strs[0];
        }
        String word = strs[0];
        int pre = 0;
        for (int i = 0; i < word.length(); i++) {
            //比较每个单词的前缀或者第i位是否相同 一旦发现不同就返回结果
            for (int n = 1; n < strs.length; n++) {
                
                if (strs[n].length() <= i || strs[n].charAt(i) != word.charAt(i)) {
                    pre = i - 1; //这就是前一个字母
                    if (pre == -1) {
                        return "";
                    }
                    return word.substring(0, pre+1); // 返回到pre的位置 不包含pre
                    
                }
            }
        }
        
        return word;
        
    }
}

参考链接

Leetcode 14. Longest Common Prefix

上一篇:信息收集总结


下一篇:业务安全漏洞挖掘归纳总结