14. 最长公共前缀

题目描述

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

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

输入输出

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

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

基本思路

按照输入输出的第一个例子 i = 1 j = 0[必须满足j<6('flower'长度) && j<4('flow'长度)]

比较flower中的逐个字符和flow中的逐个字符 如果不相等就跳出循环

性能：

  • 时复：$O(mn)$ m是字符串数组中的字符串的平均长度，n是字符串的数量
  • 空复：$O(1)$ 使用的额外空间复杂度为常数

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public String longestCommonPrefix(String[] strs) {
        int j;
        if(strs.length == 0) return "";
        String ans = strs[0];
        for(int i = 1; i < strs.length; i++) {
            for(j = 0; j < ans.length() && j < strs[i].length(); j++){
                if(ans.charAt(j) != strs[i].charAt(j)){
                    break;
                }
            }
            ans = ans.substring(0, j);
        }
        return ans;
    }
}