14. 最长公共前缀

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

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

示例 1：

1
2

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

示例 2：

1
2
3

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

提示：

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

先上我写的垃圾代码：

 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
30
31
32
33
34
35
36
37
38
39

public class Test {
    public static String longestCommonPrefix(String strs[]) {
        try {//trycatch是针对输入空字符串的情况，输出空字符串
            int len = strs[0].length();
            for (String s : strs) {//这是一个foreach循环，算出最小的长度，这样在接下来就只要循环最小的长度了
                if (s.length() < len) {
                    len = s.length();
                }
            }
            int count = -1;//用作计数
            for (int i = 0; i < len; i++) {
                char c0 = strs[0].charAt(i); //这里将第一个字符串作为标准，将后面的字符串与第一个分别比较
                for (String s : strs) {//这也是一个foreach循环
                    if (c0 != s.charAt(i)) {//一旦遇到不相等，就为count赋值，停止所有循环
                        count = i;
                        break;
                    }
                    if(i+1==len){count=i+1;}//针对情况：“ab”，“a”，循环结束仍然没有为count赋值，那就手动赋值
                }

                if ( count != -1) {//一旦count被赋值了（即不等于-1），立即break
                    break;
                }
            }//完成循环，开始输出结果

                return strs[0].substring(0, count);//如果count==-1或者0，不用担心，exception会帮我们处理掉哦
        }catch (Exception x){return "";}
    }

    public static void main(String[] args) {
        String strs[] =new String[3];
        strs[0]="floger";
        strs[1]= "flog";
        strs[2]="floght";
        System.out.println(strs.length);
        System.out.println(longestCommonPrefix(strs));

    }
}

暴力求解，逐个循环，相信你一定没心情看我的烂代码。时隔不少天我再编辑时，发现我也看不懂了。

下面给大家分享一个大神解法

img

字典序最大和最小字符串的公共前缀

悠远的苍穹L3发布于 2020-06-1514.1kC++PythonPython3

解题思路

先找出数组中字典序最小和最大的字符串，最长公共前缀即为这两个字符串的公共前缀 ~J5{I}[]G{FG3AA1KHBS5W1.png

代码

下面是 C++17 的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty()) return "";
        // c++17 结构化绑定
        // str0, str1 分别是一个 pair<string, string> 的 first 和 second
        const auto [str0, str1] = minmax_element(strs.begin(), strs.end());
        for(int i = 0; i < str0->size(); ++i)
            if(str0->at(i) != str1->at(i)) return str0->substr(0, i);
        return *str0;
    }
};

等同的 C++11 代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty()) return "";
        const auto p = minmax_element(strs.begin(), strs.end());
        for(int i = 0; i < p.first->size(); ++i)
            if(p.first->at(i) != p.second->at(i)) return p.first->substr(0, i);
        return *p.first;
    }
};

Python 代码

1
2
3
4
5
6
7
8
9

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        str0 = min(strs)
        str1 = max(strs)
        for i in range(len(str0)):
            if str0[i] != str1[i]:
                return str0[:i]
        return str0

这里关键在于minmax_elements的使用

该函数是返回指定范围内的最大最小值的元素的迭代器组成的一个pair, 如果最值多于一个， first返回的是第一个出现的最小值的迭代器，second返回的是最后一个出现的最大值的迭代器 。

下面是一个例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void minmaxelement(){
    vector<int> vi{3,5,4,1,3,1,9,9,5};
    cout<<"vi=";
    for(int i:vi)
        cout<<i<<" ";
    cout<<endl;
    auto it=minmax_element(vi.begin(),vi.end());
   cout<<" auto it=minmax_element(vi.begin(),vi.end())"<<endl;
   cout<<"*it.first="<<*it.first<<" ,*it.second="<<*it.second<<endl;
    cout<<"*(it.first-1)="<<*(it.first-1)<<" ,*(it.second-1)="<<*(it.second-1)<<endl;
}

// auto it=minmax_element(vi.begin(),vi.end())
//it.first=1 it.second=9
//*(it.first-1)=4 *(it.second-1)=9

注意 string 比较采用的是 ”字典序“，a,bc,aac按照字典序比较就是：a,aac,bc.

 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
30
31
32

template<class ForwardIt, class Compare>
std::pair<ForwardIt, ForwardIt> 
    minmax_element(ForwardIt first, ForwardIt last, Compare comp)
{
    auto min = first, max = first;
    if (first == last || ++first == last)
    return {min, max};
 
if (comp(*first, *min)) {
    min = first;
} else {
    max = first;
}
 
while (++first != last) {
    auto i = first;
    if (++first == last) {
        if (comp(*i, *min)) min = i;
        else if (!(comp(*i, *max))) max = i;
        break;
    } else {
        if (comp(*first, *i)) {
            if (comp(*first, *min)) min = first;
            if (!(comp(*i, *max))) max = i;
        } else {
            if (comp(*i, *min)) min = i;
            if (!(comp(*first, *max))) max = first;
        }
    }
}
return {min, max};
}

https://en.cppreference.com/w/cpp/algorithm/minmax_element

这是最初c语言第一节课的知识，strcmp的比较方法

comparison function object (i.e. an object that satisfies the requirements of Compare) which returns true if if *a is less than *b. The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)). The types Type1 and Type2 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to both of them.

https://en.cppreference.com/w/cpp/algorithm/minmax_element