JYT's Leetcode Solution(3)

2022-07-27

1 题目描述

题14 最长公共前缀

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

示例1

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

示例2

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

2 问题解法

2.1 显而易见的办法

乍一看，我们很容易想到比较字符串数组中各字符串的第一个字符，若全部相同，再比较第二个，以此类推。显然，此解法的时间复杂度为O(n^2)。经过测试，部分样例超出时间限制。

2.2 仔细想想

在大部分编程语言中，不仅数值型数据可以比较大小，字符串也可以比较大小。比较大小时，计算机会从前往后依次比较字符串各个字符ASCLL码值的大小，直至出现不等。那么，一个字符串数组中最大的与最小的字符串之间有什么关系呢？在示例1中，最大字符串为flower，最小字符串为flight，它们的最长公共前缀fl即为整个数组的最长公共前缀。这样的规律是普遍的。因此，我们可以先求出字符串数组的最大与最小的字符串，然后求出它们的最长公共前缀，，从而得到所求结果。此算法的时间复杂度只有O(n)。

3 求解代码

  • c++代码
    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
    29
    class Solution {
    public:
        string longestCommonPrefix(vector<string>& strs) {
            int num = strs.size();
            //求字符串数组中最大与最小的字符串
            string maxs = strs[0];
            string mins = strs[0];
            for(int i = 1; i < num; i++){
                if(strs[i] > maxs){
                    maxs = strs[i];
                }
                if(strs[i] < mins){
                    mins = strs[i];
                }
            }
            //求两字符串的最长公共前缀
            string re = "";
            int pos = 0;
            while(pos < maxs.length() && pos < mins.length()){
                if(maxs[pos] == mins[pos]){
                    re += maxs[pos];
                    pos++;
                }else{
                    break;
                }
            }
            return re;
        }
    };
  • python代码
    1
    2
    3
    4
    5
    6
    7
    8
    class Solution:
        def longestCommonPrefix(self, strs: List[str]) -> str:
            s1 = min(strs)
            s2 = max(strs)
            for i,x in enumerate(s1):
                if x != s2[i]:
                    return s2[:i]
            return s1

4 总结

找出规律，复杂度O(n^2)的算法可以化简到O(n)。