算法训练 第八周

一、最长公共前缀

1.水平扫描

首先将第一个字符串设为最长公共前缀（prefix）。遍历字符串数组中的每个字符串，滚动更新遍历到的字符串和记录的公共前缀的公共前缀。具体代码如下：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 1) {
            return strs[0];
        }
        String ss = getString(strs[0], strs[1]);
        for(int i = 2; i < strs.length; i++) {
            ss = getString(ss, strs[i]);
        }
        return ss;
    }

    public String getString(String s1, String s2) {
        StringBuilder ss = new StringBuilder("");
        for(int i = 0; i < s1.length() && i < s2.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)) {
                break;
            }
            ss.append(s1.charAt(i));
        }
        return ss.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析

• 时间复杂度：O(m * n)。
• 空间复杂度：O(1)。

2.纵向扫描

遍历字符串数组中的每个字符位置i。对于每个字符位置，比较所有字符串在该位置上的字符是否相等，如果有不相等的字符或已经到达某个字符串的末尾，则返回最长公共前缀。具体代码如下：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int i = 0;
        if(strs.length == 1) {
            return strs[0];
        }
        StringBuilder ss = new StringBuilder("");
        while(true) {
            if(i > strs[0].length() - 1) {
                return ss.toString();
            }
            char a = strs[0].charAt(i);
            for(int j = 0; j < strs.length; j++) {
                if(i > strs[j].length() - 1 || strs[j].charAt(i) != a) {
                    return ss.toString();
                }
            }
            ss.append(strs[0].charAt(i));
            i++;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析

• 时间复杂度：O(m * n)。
• 空间复杂度：O(1)。

3.分治

将字符串数组分成两半，分别求左半部分的最长公共前缀和右半部分的最长公共前缀。比较l左右的最长公共前缀，得到整个数组的最长公共前缀。具体代码如下：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        return process(strs,0,strs.length);
    }

    public String process(String[] strs, int start, int end) {
        int len = end - start;
        if(len == 0) {
            return "";
        }
        if(len == 1) {
            return strs[start];
        }
        if(len == 2) {
            return getString(strs[start], strs[start + 1]);
        }
        return getString(process(strs,start,(start + end) / 2), process(strs,(start + end) / 2, end));
    }

    public String getString(String s1, String s2) {
        StringBuilder ss = new StringBuilder("");
        for(int i = 0; i < s1.length() && i < s2.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)) {
                break;
            }
            ss.append(s1.charAt(i));
        }
        return ss.toString();
    }
}
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

复杂度分析

• 时间复杂度：O(m * n)。
• 空间复杂度：O(m log n)。