字符串處理 最長(zhǎng)公共前綴

題目

難度 ：簡(jiǎn)單

編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。

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

示例 1:

輸入: ["flower","flow","flight"]
輸出: "fl"

示例 2:

輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。

說明:

所有輸入只包含小寫字母 a-z 。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/longest-common-prefix

解析一、首先是強(qiáng)硬的一一比對(duì)

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    for i := 0; i < len(strs[0]); i++ {
        for j := 1; j < len(strs); j++ {
            if i == len(strs[j]) || strs[j][i] != strs[0][i] {
                return strs[0][:i]
            }
        }
    }
    return strs[0]
}

解析二、分步

先找出數(shù)組中字典序最小和最大的字符串，最長(zhǎng)公共前綴即為這兩個(gè)字符串的公共前綴

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
         if(strs.empty()) return "";
        // c++17 結(jié)構(gòu)化綁定
        // str0, str1 分別是一個(gè) pair<string, string> 的 first 和 second
        const auto [str0, str1] = minmax_element(strs.begin(), strs.end(),
        [](const string& str0, const string& str1){return str0 < str1;});//賦予最大最小值
        for(int i = 0; i < str0->size(); ++i)
            if(str0->at(i) != str1->at(i)) return str0->substr(0, i);//截取字符串
        return *str0;
    }
};

1.minmax_element（）函數(shù)

接受一個(gè)序列的區(qū)間作為參數(shù)，查找其中第一次出現(xiàn)的最大最小值，并以std：：pair的形式返回其迭代器（注意不是值，也不是tuple）。

vector<int>v ={633，90，67，83，2，100}；
auto X一minmax_element（v.begin（），v.end（））；
cout<<int>"min<<*x.first << endl；
cout<<"max<<*x.second <<endl；

程序的運(yùn)行結(jié)果如下：

min：2
max：633

minmax_element（）的使用風(fēng)格與標(biāo)準(zhǔn)庫的算法是一致的，需要注意的就是它的返回值，一個(gè)迭代器的pair，因此必須用first和second來訪問指向最小最大值的迭代器，并用解引用操作符“*”來獲取值。