14. 最长公共前缀

1. 题目

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

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

示例 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] 仅由小写英文字母组成

2. 思路

  • 按下标位依次读取字符串数组中的每个字符串对应下标的字符进行比对，初始化targetIndex作为对应下标，targetCh作为对应下标字符
  • 由题意已知每个字符串的最大长度为200，因此可开启循环遍历数组中每一个的字符串的对应下标值是否一致，并递增targetIndex
  • 在当遍历比对完字符串数组中的每一个字符串对应targetIndex都一致时，说明该位字符为统一前缀，因此追加至结果字符串变量result中，同时自增targetIndex变量
  • 这里需要注意的是当在每次遍历到数组第一个字符串时，需要重置targetCh字符变量
  • 同时需要注意的是，在循环遍历的过程当中，需要注意字符下标不要越界

3. 代码

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
class Solution {
    public String longestCommonPrefix(String[] strs) {
        var result = new StringBuilder();

        var targetIndex = 0;
        var targetCh = ' ';

        while (targetIndex < 200) {
            for (var i = 0; i < strs.length; ++i) {
                if (i == 0) {
                    if (strs[i].length() > targetIndex) {
                        targetCh = strs[i].charAt(targetIndex);
                    } else {
                        return result.toString();
                    }
                } 

                if (strs[i].length() <= targetIndex || strs[i].charAt(targetIndex) != targetCh) {
                    return result.toString();
                }
            }
            targetIndex++;
            result.append(targetCh);
        }

        return result.toString();
    }
}

4. 复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

image-20230805021636959