LeetCode14-最长公共前缀

解题记录
191 words , 1 mins.

题目描述

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

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

示例 1：

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

1
2
3
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 如果非空，则仅由小写英文字母组成

思路

循环比较

依次取出字符串与当前公共前缀进行比对，如果前缀都匹配，则公共前缀往后拼接一个字符，再次循环比对，重复此过程直到不匹配或公共前缀长度等于最小字符串的长度。

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
class Solution {
    public String longestCommonPrefix(String[] strs) {
        String commonPrefix = "";
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            if (str.length() < minLength) {
                minLength = str.length();
            }
        }

        while (true) {
            boolean allPassFlag = true;
            for (String str : strs) {
                if (str.length() == 0) {
                    return "";
                }

                if (!str.startsWith(commonPrefix)) {
                    allPassFlag = false;
                    break;
                }
            }

            if (!allPassFlag) {
                return commonPrefix.substring(0, commonPrefix.length() - 1);
            } else {
                int length = commonPrefix.length();
                if (length >= minLength) {
                    return commonPrefix;
                }

                commonPrefix = commonPrefix + strs[0].charAt(length);
            }
        }
    }
}

更好的解法

采用递推的方式，先求 strs[0] 与 strs[1] 的最长公共前缀，再求 strs[1] 与 strs[2] 的最长公共前缀。