NC55：最长公共前缀

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/

解法1：对字符串数组进行排序，然后只要比较首尾两个字符串即可

import java.util.*;
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0)
            return "";
        Arrays.sort(strs);

        int len = strs.length;
        int l = Math.min(strs[0].length(), strs[len - 1].length());
        int i = 0;
        for(i = 0; i < l; i++){
            if(strs[0].charAt(i) != strs[len - 1].charAt(i))
                break;
        }
        return strs[0].substring(0,i);
    }
}

解法2：横向扫描

图片说明
基于该结论，可以得到一种查找字符串数组中的最长公共前缀的简单方法。依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀：
图片说明
如果在尚未遍历完所有的字符串时，最长公共前缀已经是空串，则最长公共前缀一定是空串，因此不需要继续遍历剩下的字符串，直接返回空串即可。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    public String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }
}

解法3：垂直扫描法：按列扫描，先验证所有字符串的第一个元素

纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
图片说明

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

复杂度分析

时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度：O(1)。使用的额外空间复杂度为常数。

解法4：分治

图片说明

//分治算法，在水平扫描法的基础上改进
  public static String longestCommonPrefix3(String[] strs) {
      if (strs == null || strs.length == 0)
          return "";

      return Solution(strs, 0, strs.length - 1);
  }

  public static String Solution(String[] strs, int begin, int end) {
      if(begin == end) {
          return strs[begin];
      }
      else {
          int mid = (begin + end) >> 1;
          String str1 = Solution(strs, begin, mid);
          String str2 = Solution(strs, mid + 1, end);
          if(str1 == "" || str2 == "") return "";

          int idx = -1;
          while(idx < str1.length() - 1 && idx < str2.length() - 1) {
              if(str1.charAt(idx + 1) == str2.charAt(idx + 1)) {
                  idx++;
              }else {
                  break;
              }
          }
          if(idx == -1) return "";
          return strs[begin].substring(0, idx + 1);
      }
  }

解法5：二分查找算法

图片说明

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }
        int low = 0, high = minLength;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (isCommonPrefix(strs, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return strs[0].substring(0, low);
    }

    public boolean isCommonPrefix(String[] strs, int length) {
        String str0 = strs[0].substring(0, length);
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            String str = strs[i];
            for (int j = 0; j < length; j++) {
                if (str0.charAt(j) != str.charAt(j)) {
                    return false;
                }
            }
        }
        return true;
    }
}