从零学算法14

14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1：
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
示例 2：
输入：strs = [“dog”,“racecar”,“car”]
输出：“”
解释：输入不存在公共前缀。
提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

• 最容易想到的思路就是先默认第一个字符串为结果 res，然后遍历剩下的字符串，不断根据 res 以及 str 的比较得到新的 res，这样就相当于比较了所有字符串，最终 res 就是公共前缀

•   public String longestCommonPrefix(String[] strs) {if(strs.length == 0)return "";String res = strs[0];for(int i = 1; i < strs.length; i++){res = getPre(res, strs[i]);if("".equals(res))break;}return res;}public String getPre(String s1, String s2){int min = Math.min(s1.length(), s2.length());int i = 0;while(i < min && s1.charAt(i) == s2.charAt(i)){i++;}return s1.substring(0, i);}
  

• 既然有横向的，那么纵向的也比较容易想到，取任意一个字符串为例，从第一位开始，比较所有字符串某一位是否等于该字符的这一位，需要注意的是不仅当遇到不同字符时需要返回，当某个字符串已经被比较完也应该返回

•   public String longestCommonPrefix(String[] strs) {if(strs.length == 0)return "";for(int i = 0; i < strs[0].length(); i++){char c = strs[0].charAt(i);for(int j = 1; j < strs.length; j++){if(i == strs[j].length() || strs[j].charAt(i) != c){return strs[0].substring(0, i);}}}// 理论上来说返回什么都可以，因为上面的情况已经包含了比较完的情况// 但是 strs 只有一个字符串时就不会进入比较// 所以需要返回 strs[0]return strs[0];}
  

• 分治：由于不管怎么样最终每个字符都会被比较，比如第一种解法就是不断更新两个字符串比较后的结果，那么其实分治也可以，不过同时比较两组字符串而已

•   public String longestCommonPrefix(String[] strs) {if(strs.length == 0)return "";return longestCommonPrefix(strs, 0, strs.length - 1);}// 分治public String longestCommonPrefix(String[] strs, int start, int end) {if(start == end)return strs[start];int mid = start + (end - start) / 2;String left = longestCommonPrefix(strs, start, mid);String right = longestCommonPrefix(strs, mid + 1, end);return commonPrefix(left, right);}// 获取两个字符串的公共前缀public String commonPrefix(String lcpLeft, String lcpRight) {int minLength = Math.min(lcpLeft.length(), lcpRight.length());       for (int i = 0; i < minLength; i++) {if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {return lcpLeft.substring(0, i);}}return lcpLeft.substring(0, minLength);}
  

• 二分法：由于最终公共前缀的长度不会大于最短字符串长度 min ，那么可以在解法 2 的基础上，使用二分法，从 left = 0 ，right = min 开始，得到最终公共前缀的长度

•   public String longestCommonPrefix(String[] strs) {if(strs.length == 0)return "";int min = Integer.MAX_VALUE;for (String str : strs) {min = Math.min(min, str.length());}int left = 0, right = min;while(left < right){int mid = left + (right - left + 1) / 2;if(isCommonPrefix(strs, mid))left = mid;else right = mid - 1;}return strs[0].substring(0, left);}// 判断 length 是否为公共前缀public boolean isCommonPrefix(String[] strs, int length) {    for (int i = 0; i < length; i++) {char c = strs[0].charAt(i);for(int j = 1; j < strs.length; j++){if(strs[j].charAt(i) != c)return false;}}return true;}