LeetCode-14. 最长公共前缀

题目来源

14. 最长公共前缀

题目详情

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

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

示例 1：

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

示例 2：

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

提示：

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

题解分析

解法一：纵向扫描

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        StringBuilder sb = new StringBuilder();
        for(int i=0; i= strs[j].length() || ch != strs[j].charAt(i)){
                    flag = false;
                    break;
                }
            }
            if(flag){
                sb.append(ch);
            }else{
                break;
            }
        }
        return sb.toString();
    }
}

解法二：横向扫描

根据公共前缀的特点，可以总结出以下的公式：

\[L C P\left(S_{1} \ldots S_{n}\right)=L C P\left(L C P\left(L C P\left(S_{1}, S_{2}\right), S_{3}\right), \ldots S_{n}\right) \]

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        String pre = strs[0];
        for(int i = 1; i

结果展示