leetcode 14 Longest Common Prefix
z
 2017-12-16 11:08:08  

###14. Longest Common Prefix

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

  • 最初始的想法是，取第一个string出来，和之后的每一个进行比较，得到第一个String 和之后的String 的common Prefix substring的index，取最小值。在这种情况下，需要考虑一下几点
    • 当输入没有string时，return “”
    • 当输入只有一个string时，return string[0], 或者将第一个for语句从i=0开始。
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
class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length; // 获得总共的string数目
        if ( n == 0){ // 输入特例，当没有输入string时
            return "";
        }
        if (n == 1){ // 输入特例，当输入只有一个string时
            return strs[0];
        }
        int index = 0; // 记录每次strs[i]和strs[0]比较时的index
        int min = Integer.MAX_VALUE;// 用于得到所有比较中最小的那个
                
        for (int i=1;i<n;i++){ // 从第二个string开始比较
            for (int j=0; j< Math.min(strs[0].length(),strs[i].length());j++){ //考虑j的范围，应该小于第一个和当前比较的第i个的最短
                if(strs[0].charAt(j) != strs[i].charAt(j)){// 不等时，结束当前比较
                    // index = j 不能放在这里，当比较下来没有进入这个if时，index得不到赋值。
                    break;
                }
                index ++;// 相等时，index++
            }
            min = Math.min(min, index); // 保存当前比较得到的最小值
            index = 0;// 记得将index归零
        }
        return strs[0].substring(0, min);
    }
}

记录下另外一种解法：

  • 先对strs进行排序，在这种情况下，只需要比较第一个String和最后一个string
  • 这种方法相对于上面的方法，要更快一些(11ms)上面的大概是15、16ms。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0){ // 特例输入长度为0的情况
            return "";
        }
        Arrays.sort(strs);// 对strs进行排序，小的在前，大的在后
        String first = strs[0];
        String last = strs[strs.length-1];
        for(int i=0; i<first.length(); i++){
            if (first.charAt(i) != last.charAt(i)){
                return last.substring(0, i);
            }
        }
        return first;// 如果完全一样，返回排序后的第一个就好
    }
}
  • Arrays.sort()实现的是并归排序，时间复杂度为O(nlogn)
  • 排序后是按生序排列的，因此最小的数在第一个，所以这里for循环只需要去i<firs.length()
  • 注意： 对于String[] a，想要获得a中string的个数，使用a.length,其中想要获得第i个String，使用a[i],对于第i个String，想要获得其字符个数，使用a[i].length().