文章

LeetCode Longest Common Prefix

Problem

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

就是找出一个字符串数组中元素,最长的通用前缀。例如:{“ab”,”abc”,”abd”},答案是 “ab”。

Java 实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package com.coderli.leetcode.algorithms.easy;

import java.util.Arrays;

/**
 * Write a function to find the longest common prefix string amongst an array of strings.
 *
 * @author li.hzh
 */
public class LongestCommonPrefix {

    public static void main(String[] args) {
        LongestCommonPrefix longestCommonPrefix = new LongestCommonPrefix();
        System.out.println(longestCommonPrefix.longestCommonPrefix(new String[]{"a"}));
        System.out.println(longestCommonPrefix.longestCommonPrefix(new String[]{"a", "ab", "abc"}));
        System.out.println(longestCommonPrefix.longestCommonPrefix(new String[]{"abc", "ab", "abc"}));
        System.out.println(longestCommonPrefix.longestCommonPrefix(new String[]{"abd", "ab", "abc"}));
        System.out.println(longestCommonPrefix.longestCommonPrefix(new String[]{"a", "b", "c"}));
    }

    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String result = strs[0];
        for (int i = 1; i < strs.length; i++) {
            String currentStr = strs[i];
            int findLength = Math.min(result.length(), currentStr.length());
            int commonLength = 0;
            for (int j = 0; j < findLength; j++) {
                char charInResult = result.charAt(j);
                char charInCurrent = currentStr.charAt(j);
                if (charInResult == charInCurrent) {
                    commonLength++;
                } else {
                    break;
                }
            }
            result = result.substring(0,commonLength);
        }
        return result;
    }

    public String longestCommonPrefixBySortFirst(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        Arrays.sort(strs);
        String first = strs[0];
        String second = strs[strs.length - 1];
        String result = first;
        int commonLength = 0;
        for (int j = 0; j < first.length(); j++) {
            char charInFirst = result.charAt(j);
            char charInSecond = second.charAt(j);
            if (charInFirst == charInSecond) {
                commonLength++;
            } else {
                break;
            }
        }
        result = result.substring(0,commonLength);
        return result;
    }

}



分析

这里提供了两个解法。第一个解法longestCommonPrefix,应该最容易被想到的解法。就是直接暴力的遍历数组元素,拿每个元素跟当前结果做前缀比较。找出最新的最大前缀。输出结果。需要注意处理一下边界值就ok。

提供第二个解法longestCommonPrefixBySortFirst是因为,第一个解法测试虽然通过,但效率不高。因为考虑优化性能,减少遍历。因此采用先排序再比较的做法。这样只需要拿排序后的数组的第一位和最后一位比较即可。减少一次遍历,但是增加了一次排序损耗。不过快排一般来说是O(nlgn)的,而后一次的遍历,遍历的只是数组最短长度元素的长度,因此提升了一些效率。

最后,我也查看一下提交里效率较高解法,主要的优化在于前缀计算上。参考代码如下:

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

本文由作者按照 CC BY 4.0 进行授权