最长公共前缀 - 《数据结构与算法》

题目链接 https://leetcode.cn/problems/longest-common-prefix/
测试用例 ```java @Test public void test_longestCommonPrefix_success() { String[] ss = new String[] {“flight”, “flice”, “flite”, “fliace”}; Assert.assertEquals(“fli”, longestCommonPrefix(ss)); }

@Test public void test_longestCommonPrefix_fullWords() { String[] ss = new String[] {“flight”, “flight”, “flight”}; Assert.assertEquals(“flight”, longestCommonPrefix(ss)); }

@Test public void test_longestCommonPrefix_empty() { String[] ss = new String[] {“flight”, “fly”, “acquire”}; Assert.assertEquals(“”, longestCommonPrefix(ss)); }

@Test public void test_longestCommonPrefix_oneChar() { String[] ss = new String[] {“a”, “b”, “c”}; Assert.assertEquals(“”, longestCommonPrefix(ss)); }


3. 方法签名
```java
public String longestCommonPrefix(String[] ss);

横向比较

比较前两个字符串的公共前缀 prefix 和第三个字符串再做比较，遍历比较全部元素得到最终的最长公共前缀。如果中途前缀变为空字符串，提前终止程序。

public static String longestCommonPrefix(String[] ss) {
    if (ss == null || ss.length == 0) {
        return "";
    }
    String prefix = ss[0];
    for (int i = 1; i < ss.length; i++) {
        prefix = commonPrefix(prefix, ss[i]);
        if (prefix.length() == 0) {
            break;
        }
    }
    return prefix;
}
protected static String commonPrefix(String a, String b) {
    int i = 0;
    while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) {
        i++;
    }
    return a.substring(0, i);
}

纵向比较

比较所有字符串的每一列字符是否相同，最长公共前缀是第一个字符串的子串，遍历第一个字符串每一列，比较如果和其他字符串当前列相同继续比较下一列，直到不相同或长度超过字符串。

public static String longestCommonPrefix(String[] ss) {
    if (ss == null || ss.length == 0) {
        return "";
    }
    String prefix = ss[0];
    for (int i = 0; i < prefix.length(); i++) {
        for (int j = 1; j < ss.length; j++) {
            if (ss[j].length() == i || prefix.charAt(i) != ss[j].charAt(i)) {
                prefix = prefix.substring(0, i);
                break;
            }
        }
    }
    return prefix;
}

分治算法

分开比较左右子字符串数组分别求最长公共前缀 prefix_left 和 prefix_right，两者再求最终公共前缀。

public static String longestCommonPrefix(String[] ss) {
        if (ss == null || ss.length == 0) {
            return "";
        }
        return longestCommonPrefix(ss, 0, ss.length-1);
    }
private static String longestCommonPrefix(String[] ss, int start, int end) {
    if (start == end) {
        return ss[start];
    }
    int mid = (start+end) >>> 1;
    String left = longestCommonPrefix(ss, start, mid);
    String right = longestCommonPrefix(ss, mid + 1, end);
    return commonPrefix(left, right);
}
private static String commonPrefix(String a, String b) {
    int i = 0;
    while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) {
        i++;
    }
    return a.substring(0, i);
}

二分查找

最长公共前缀的长度不会超过数组中最短字符串长度 minLen。最长公共前缀长度在 [0,minLen] 范围内，每次取长度中间值 mid，判断所有字符串的前 mid 长度字符是否相同。

如果相同最长公共前缀长度一定大于等于 mid
如果不相同最长公共前缀长度一定小于 mid ```java 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; } ```