14. 最长公共前缀


14. 最长公共前缀

难度简单 1479
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""

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

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

提示:

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成.
public String longestCommonPrefix(String[] strs) &#123;
        if (strs == null || strs.length == 0) &#123;
            return "";
        &#125;
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) &#123;
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) &#123;
                break;
            &#125;
        &#125;
        return prefix;
    &#125;

    public String longestCommonPrefix(String str1, String str2) &#123;
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) &#123;
            index++;
        &#125;
        return str1.substring(0, index);
    &#125;

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
class Solution &#123;
    public String longestCommonPrefix(String[] strs) &#123;
        if (strs == null || strs.length == 0) &#123;
            return "";
        &#125;
        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) &#123;
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) &#123;
                if (i == strs[j].length() || strs[j].charAt(i) != c) &#123;
                    return strs[0].substring(0, i);
                &#125;
            &#125;
        &#125;
        return strs[0];
    &#125;
&#125;

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/

解析

方法一是横向扫描,依次遍历每个字符串,更新最长公共前缀。
方法二是纵向扫描。纵向扫描时,从前往后遍历所有字符串的每一列,比较相同列上的字符是否相同,如果相同则继续对下一列进行比较,如果不相同则当前列不再属于公共前缀,当前列之前的部分为最长公共前缀


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
922. 按奇偶排序数组 II 922. 按奇偶排序数组 II
922. 按奇偶排序数组 II难度简单 191给定一个非负整数数组 A, A 中一半整数是奇数,一半整数是偶数。对数组进行排序,以便当 A[i] 为奇数时,i 也是奇数;当 A[i] 为偶数时, i 也是偶数。你可以返回任何满足上述条件的数
2021-03-02 future
下一篇 
剑指 Offer 61. 扑克牌中的顺子 剑指 Offer 61. 扑克牌中的顺子
剑指 Offer 61. 扑克牌中的顺子难度简单 98从扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这 5 张牌是不是连续的。2 ~ 10 为数字本身,A 为 1,J 为 11,Q 为 12,K 为 13,而大、小王为 0 ,可以看成任
  目录