leetcode 14. 最长公共前缀 java_leetcode 公共前缀 java

题目：最长公共前缀

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

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

示例 1:

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

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

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

---

分析：

思路：算是暴力法吧。寻找字符串数组中最短的那个作为比较标杆，按照这个字符串一个个字符比较过去即可。然后找出不用比较可直接返回答案的情况提出来：当字符串数组只有一个元素或者没有元素时。

注意：字符串数组中允许的最短的符串长度为0，最终截取字符串时要注意。

代码：

public String longestCommonPrefix(String[] strs) {
        if (strs.length<2) return strs.length==0?"":strs[0];
        //1.找到数组中最短的字符串，并记录位置
        int minLen=strs[0].length(),minSub=0;
        for(int i=1;i<strs.length;i++){
            if (strs[i].length()<minLen){
                minLen=strs[i].length();
                minSub=i;
            }
        }
        if (minLen==0) return "";//这步也可以和返回语句合并在一起
        //2.比照最短的字符串，一个个和其他字符串比较，找到最长公共前缀的长度
        // 并在找到的最短字符串字符串中截取该长度作为最长公共前缀作为返回值
        int maxLen=0;
        boolean flag=true;//记录该字符是不是公共前缀
        for (int i=0;i<minLen;i++){
            char ch=strs[minSub].charAt(i);
            flag=true;
            for (int j=0;j<strs.length;j++){
                if (strs[j].charAt(i) != ch){
                    flag=false;
                    break;
                }
            }
            if (flag==true)
                maxLen++;
            else
                break;
        }

        return strs[minSub].substring(0,maxLen);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

执行用时 :1 ms, 在所有 Java 提交中击败了80.24%的用户。

比预想的要好，毕竟我用来了一个双层循环。想了想，大概是因为数据的问题，虽然光看算法时间复杂度是O(n²)，但因为数据短且少，所以运行起来时间很短。如果最短字符串很长的话，就很花费时间了。
 

学习：

官方给了四种答案。

• 算法一，水平扫描法：前两个字符串找公共前缀，将其结果和第三个字符串找公共前缀……直到最后一个串。（找公共前缀：通过做减法运算，如fly是不是flow的前缀，不是，那fl是不是flow的前缀，ok，找到，记住fl）

  核心思想：通过给字符串做减法来找前缀，从左到右扫描判断公共前缀。

  执行时间在0ms—1ms之间。

  代码：

public static 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){
                prefix=prefix.substring(0,prefix.length()-1);
                if (prefix.length()==0) return "";
            }
        }
        return prefix;
}
1
2
3
4
5
6
7
8
9
10
11

• 算法二，垂直扫描法：从前往后枚举字符串的每一列，先比较每个字符串相同列上的字符（即不同字符串相同下标的字符）然后再进行对下一列的比较。

  核心思想：一列一列扫描。

  为了理解方便，我给改了名，官方管这个算法叫“水平扫描”，但我觉得这样没法和算法一区分开，而且不形象，叫垂直扫描比较妥帖。

  这个和我的算法基本类似，相比较起来，我的稍微在这个的基础上做了优化，以为我是选择的最短的字符串作为标杆。这样，在字符串元素长度差异大的情况下，能节省时间，但在字符串元素长度比较平均的情况下，我的会白做工一个循环的时间。

• 算法三，分治法：看图即可

  核心思想：将字符串数组分组寻找公共前缀，最后汇合。
  

• 算法四，二分查找法：看图即可

  核心思想：将作为标杆的字符串分组，一块一块比较。
  

总结：

1. 利用api 判断某字符串的首字符(串)是不是所需的字符（串）：indexOf(s)==0

   public int indexOf(String str)

2. 关于字符串问题的算法如何考虑周全，少bug，少漏用例：
   ① 先考虑一般情况，将一般情况的处理步骤理顺，整理成可执行的算法；
   ② 考虑简单情况，即无需计算即可返回结果的情况，一般需要考虑以下情况：
        a.字符串为空（""）
        b.字符串数组为空（没有元素）
        c.字符串数组远元素少到不需要计算，或字符串长度短到不需要计算，这个数量根据题目定，一般是1或2
   ③ 看一般情况和特殊情况加起来有没有包括所能想到的所有用例；
   ④ 考虑取字符和字符串的越界可能，如charAt()、substring()，取的位置不能超过字符串长度，不能取空字符串。