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;
    }
}