[leetcode] 14. 最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例 1：
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”

示例 2：
输入：strs = [“dog”,“racecar”,“car”]
输出：“”
解释：输入不存在公共前缀。

提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

解题方法

这个题目比较简单，其实存在不少解发，没必要全部列出来，下面只说一种我的解法吧。

纵向扫描

从前往后遍历所有字符串的每一列。如果字符都相同，则把该字符加到公共前缀中；如果存在不同的字符，则当前列不再属于公共前缀，该列之前的所有字符即为最长公共前缀。

java代码

public String longestCommonPrefix(String[] strs) {
    StringBuilder prefixBuilder = new StringBuilder();
    int l = 0;
    boolean flag = true;
    while(flag) {
        char c = ' ';
        for(int i = 0; i < strs.length; i++) {
            if(strs[i] == null) {
                flag = false;
                break;
            }
            if(l == strs[i].length()) {
                flag = false;
                break;
            }
            char sc = strs[i].charAt(l);
            if(c == ' ') {
                c = sc;
            } else if (sc != c) {
                flag = false;
                break;
            }
            if(i == strs.length - 1) {
                prefixBuilder.append(c);
                l++;
            }
        }
    }
    return prefixBuilder.toString();
}

时间复杂度：$O(MN)$，$M$为字符串平均长度，$N$为字符串数组长度。
空间复杂度：$O(1)$。

• 个人公众号
  
• 个人小游戏