【LeetCode】No.14. Longest Common Prefix -- Java Version

题目链接： https://leetcode.com/problems/longest-common-prefix/

1. 题目介绍（最长通用前缀）

Write a function to find the longest common prefix string amongst an array of strings.

【Translate】： 编写一个函数，在字符串数组中找出最长的公共前缀字符串。

If there is no common prefix, return an empty string “”.

【Translate】： 如果没有公共前缀，则返回空字符串""。

【测试用例】：

【约束】：

2. 题解 2.1 遍历最小长度的前缀可能元素 – O(n²)

  该题解的基本思想就是先找出字符串数组中最小长度的字符串，然后根据它的长度进行比较，防止遍历的时候数组越界，其根本上是穷举的思想。

    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        StringBuilder sb = new StringBuilder();
        int minLen = 200;
        if(n == 1){
            return strs[0];
        }
        
        for(int i = 0 ; i < n; i++)
        {
            if(strs[i].length() < minLen){
                minLen = strs[i].length();
            }
        }
        
        for (int i = 0; i < minLen; i++)
        {
            
            for (int j = 1; j < n; j++)
            {
                if (!(strs[0].charAt(i) == strs[j].charAt(i)) && sb.length() == 0){
                    // System.out.println(strs[j].charAt(i));
                    return "";
                }else if (!(strs[0].charAt(i) == strs[j].charAt(i)) && sb.length() > 0){
                    return sb.toString();
                }
            }
            sb.append(strs[0].charAt(i));
            // System.out.println(strs[0].charAt(i));
           
        }
        return sb.toString();
    }

2.2 Horizontal scanning – O(S)

  Solution Approach 1，其思想就是冒泡式比较，取相同前缀元素。

 public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++)
        while (strs[i].indexOf(prefix) != 0) { // 如果此字符串中没有这样的字符，则返回 -1
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}

2.3 Vertical scanning – O(S)

  Solution Approach 2，假设一个非常短的字符串是数组末尾的公共前缀。上述方法仍然会进行S次比较。优化这种情况的一种方法是做垂直扫描。在移到下一列之前，我们从上到下比较同一列(字符串的相同字符索引)上的字符，类似于2.1。

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || 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);             
            }
        }
        return strs[0];
    }

2.4 Divide and conquer – O(S)

  Solution Approach 3.

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";    
        return longestCommonPrefix(strs, 0 , strs.length - 1);
}

private String longestCommonPrefix(String[] strs, int l, int r) {
    if (l == r) {
        return strs[l];
    }
    else {
        int mid = (l + r)/2;
        String lcpLeft =   longestCommonPrefix(strs, l , mid);
        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
        return commonPrefix(lcpLeft, lcpRight);
   }
}

String commonPrefix(String left,String right) {
    int min = Math.min(left.length(), right.length());       
    for (int i = 0; i < min; i++) {
        if ( left.charAt(i) != right.charAt(i) )
            return left.substring(0, i);
    }
    return left.substring(0, min);
}

3. 可参考

[1] Java String indexOf() 方法
[2] LeetCode Longest Common Prefix Solution