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

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

示例 1:

输入: [“flower”,”flow”,”flight”] 输出: “fl” 示例 2:

输入: [“dog”,”racecar”,”car”] 输出: “” 解释: 输入不存在公共前缀。 说明:

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

有三种解法：

  • 排队减尾法(从后往前)
  • 排队比较法(从前往后)
  • 噶韭菜法(从前往后循环，一次循环确定1位)

排队减尾法(从后往前)

  1. class Solution {
  2.     public String longestCommonPrefix(String[] strs) {
  3.         if (strs.length == 0) return "";
  4.         String ans = strs[0];
  5.         // ans = str[0]
  6.         // 遍历Str[1]···str[str.length-1]
  7.         // 在遍历中，对str不停剪尾，直到str中不包含ans
  8.         // 如果有一个减到头了，直接返回""
  9.         for (int i = 1; i < strs.length; i++)
  10.             while (strs[i].indexOf(ans) != 0) {
  11.                 ans = ans.substring(0, ans.length() - 1);
  12.                 if (ans.isEmpty()) return "";
  13.             }
  14.         return ans;
  15.     }
  16. }

逐步收缩法

  1. class Solution {
  2.     public String longestCommonPrefix(String[] strs) {
  3.         if(strs.length==0){
  4.             return "";
  5.         }
  6.         String ans = strs[0];
  7.         for(int i = 1;i < strs.length;i++){
  8.             int j = 0;
  9.             while(j < ans.length() &&  j < strs[i].length()){
  10.                 if(ans.charAt(j) != strs[i].charAt(j))
  11.                     break;
  12.                 j++;
  13.             }
  14.             ans = ans.substring(0, j);
  15.         }
  16.         return ans;
  17.     }
  19. }

噶韭菜法(从前往后循环，一次循环确定这一位及之后的字符是否不可保留)

  1. class Solution {
  2.     public String longestCommonPrefix(String[] strs) {
  3.         if (strs==null||strs.length==0) return "";
  4.         //官网水平搜索
  5.         for(int i=0;i<strs[0].length();i++){
  6.             char c=strs[0].charAt(i);
  7.             for(int j=1;j<strs.length;j++){
  8.                 if(i==strs[j].length() || strs[j].charAt(i)!=c)
  9.                     return strs[0].substring(0,i);
  10.             }
  11.         }
  12.         return strs[0];
  13.     }
  14. }