C++如何實(shí)現(xiàn)最長(zhǎng)公共前綴

這篇文章主要為大家展示了“C++如何實(shí)現(xiàn)最長(zhǎng)公共前綴”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“C++如何實(shí)現(xiàn)最長(zhǎng)公共前綴”這篇文章吧。

一、題目描述

編寫(xiě)一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。
如果不存在公共前綴，返回空字符串 ""。

示例 1：
輸入：strs = ["flower","flow","flight"]輸出："fl"示例 2：
輸入：strs = ["dog","racecar","car"]輸出：""解釋?zhuān)狠斎氩淮嬖诠睬熬Y。

提示：0 <= strs.length <= 2000 <= strs[i].length <= 200strs[i] 僅由小寫(xiě)英文字母組成

二、解題思路

(1) 橫向遍歷法

解題思路：

如下圖所示，依次遍歷字符串?dāng)?shù)組中的每一個(gè)字符串：

具體步驟如下：

• 先計(jì)算前兩個(gè)元素S1和S2的最長(zhǎng)公共前綴LSP(S1,S2)，記為S1

• 再計(jì)算是S1與S3的最長(zhǎng)公共前綴LSP(S1,S3)，記為S1

• 依次下去，當(dāng)遍歷完所有的字符串以后，即可得到字符串?dāng)?shù)組中的最長(zhǎng)公共前綴

• 如果在還未遍歷完所有字符串，最長(zhǎng)公共前綴已經(jīng)是空串，則最長(zhǎng)公共前綴一定是空串，因此不需要繼續(xù)遍歷剩下的字符串，直接返回空串即可。

C++實(shí)現(xiàn)如下：

class Solution {
   
   
   public:string longestCommonPrefix(vector<string>& strs) {
   
   
   if(!strs.size()) return "";string s1 = strs[0]; //初始化for(int i=1; i<strs.size(); ++i){
   
   
   s1 = lcp(s1, strs[i]); //計(jì)算兩字符串的最大公共前綴if(!s1.size()) break; //如果沒(méi)有公共字符，則最長(zhǎng)公共前綴一定是空串}return s1;}//計(jì)算兩字符串的最大公共前綴string lcp(const string& str1, const string& str2){
   
   
   int len = min(str1.size(), str2.size());int index = 0;while(index < len && str1[index] == str2[index]){
   
   
   ++index;}return str1.substr(0, index);}};

測(cè)試結(jié)果：

復(fù)雜度分析；

• 時(shí)間復(fù)雜度：O(mn)，其中 m 是字符串?dāng)?shù)組中的字符串的平均長(zhǎng)度，n 是字符串的數(shù)量。最壞情況下，字符串?dāng)?shù)組中的每個(gè)字符串的每個(gè)字符都會(huì)被比較一次。

• 空間復(fù)雜度：O(1)。使用的額外空間復(fù)雜度為常數(shù)。

注：根據(jù)數(shù)據(jù)范圍可知，處理一次該函數(shù)最多需要200x200=4x10^4次操作。如果計(jì)算機(jī)一秒能處理10e6次，那么該函數(shù)處理一次最多耗時(shí)0.04s

(2) 縱向遍歷法

解題思路：

如下圖所示，將字符串?dāng)?shù)組按照如下方式橫向擺布：

具體步驟如下：

• 按照縱向方向遍歷，判斷所有字符串的第i個(gè)元素strs[][i]是否相等，如果相等繼續(xù)遍歷

• 如果不相等，停止遍歷，并返回前i個(gè)公共的字符：strs[0].substr(0, i+1)

C++代碼如下:

class Solution {
   
   
   public:string longestCommonPrefix(vector<string>& strs) {
   
   
   string out_str;if(!strs.size()) return "";int len = strs[0].size();//第一個(gè)字符串的長(zhǎng)度f(wàn)or(int i=0; i<len; ++i){
   
   
   for(int j=1; j<strs.size(); ++j){
   
   
   if(strs[j][i]!=strs[0][i])return out_str;}out_str = strs[0].substr(0, i+1);}return out_str;}};

測(cè)試結(jié)果：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(nm)，其中 m 是字符串?dāng)?shù)組中的字符串的平均長(zhǎng)度，n 是字符串的數(shù)量。

• 空間復(fù)雜度：O(1)，使用的額外空間復(fù)雜度為常數(shù)。

以上是“C++如何實(shí)現(xiàn)最長(zhǎng)公共前綴”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！