LeetCode-14 最长公共前缀

「爱情、让人受尽委屈。」 2022-03-30 14:42 243阅读 0赞

### 文章目录 ###

*   *   *  题目描述
         *  我的解法
         *  反思1
         *  优化1
         *  反思2
         *  优化2
         *  其他思路
         *  总结
         *  Github

### 题目描述 ###

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1:

> 输入: \[“flower”,“flow”,“flight”\]  
> 输出: “fl”

示例 2:

> 输入: \[“dog”,“racecar”,“car”\]  
> 输出: “”

解释: 输入不存在公共前缀。  
说明:

所有输入只包含小写字母 a-z 。

--------------------

### 我的解法 ###

public String longestCommonPrefix(String[] strs) { 
            //特殊情况
            if(null == strs||0 == strs.length)//字符数组为空的情况
                return "";
            if(1 == strs.length)//数组中只有一个字符串，那么前缀就是他本身
                return strs[0];
    
            boolean finalRound = false;
            boolean isPlusIndex = true;
            int index = 0;
    
            while(!finalRound){ 
                for(int i=1; i<strs.length; i++){ 
                    if(index > strs[i-1].length() ||index > strs[i].length()){ //如果超出某个字符串长度了，终止//这个也同时校验了某一个字符串为空的情况
                        finalRound = true;
                        isPlusIndex = false;
                        break;
                    }
                    if(strs[i-1].substring(0,index).equals(strs[i].substring(0,index))) { 
    
                    }  else{ //如果前缀不相等了，终止
                        finalRound = true;
                        isPlusIndex = false;
                        break;
                    }
                }
    
                if(isPlusIndex)
                    index++;
            }
    
            return strs[0].substring(0,index-1);//因为我把最开始假设多了一位“”，所以实际的索引要减去一
        }

用间：9ms  
战胜：77.55%

--------------------

### 反思1 ###

1.  其实可以单拿出数组中第一个字符串作为标准，让其与之后的字符串进行比较。如果有相同前缀，第一个字符串必然也有。若前缀不同则可以直接return “”。
2.  我们在拿第一个字符串为标准比较前缀的时候。举个例子，比如第一个字符串和第二字符串前5位都是一致的，但是在跟第三个字符串比较的时候只有前三位一致。也就是说，我们的前缀字节数应该是随着遍历的深度越来越少。这样如果我们还是从字符串的第一个字节开始比较的话，很大几率我们的前几位字符都是一样的，这样就浪费了一些时间。相反我们从字符串的末位字符开始比较，则很快能筛掉不一致的字符。

--------------------

### 优化1 ###

public String longestCommonPrefix3(String[] strs) { 
           if(strs.length == 0) return "";
           String prefix = strs[0];
           for (int i = 0; i <= strs.length - 1; i++){ 
               while(!strs[i].startsWith(prefix)){ 
                   prefix = prefix.substring(0,prefix.length()-1);
               }
           }
           return prefix;
       }

用时：9ms  
战胜：77.55%  
==! 在我的电脑上并没有看出太大的差距

--------------------

### 反思2 ###

1.  首先我们拿第一个字符串作为标准，就没有必要再让他跟自己比较了
2.  如果发现没有公共前缀，直接跳出循环，减少系统开销

--------------------

### 优化2 ###

public String longestCommonPrefix4(String[] strs) { 
           if(strs.length == 0 || strs[0].length() == 0) return "";
           String prefix = strs[0];
           for (int i = 1; i <= strs.length - 1; i++){ 
               if(!"".equals(prefix)){ 
                   while(!strs[i].startsWith(prefix)){ 
                       prefix = prefix.substring(0,prefix.length()-1);
                   }
               }
           }
           return prefix;
       }

用时：6ms  
战胜：98.61%

--------------------

### 其他思路 ###

我比较喜欢这优化的版本，虽然leetcode上有更快的版本（并没有觉得有什么可圈可点的地方，跑出了4ms估计是网络电脑的原因，我本机还是跑了9ms）。但是少量的代码更加意味着思路的清晰。有时候这才是更重要的。

--------------------

### 总结 ###

有的时候找前面相似的问题，从末位排除是更好的办法。

--------------------

### Github ###

[LeetCode刷题笔记][LeetCode]

[LeetCode]: https://github.com/Meidanlong/LeetCode