C++如何實現最長公共前綴

這篇文章主要為大家展示了“C++如何實現最長公共前綴”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“C++如何實現最長公共前綴”這篇文章吧。

一、題目描述

編寫一個函數來查找字符串數組中的最長公共前綴。
如果不存在公共前綴，返回空字符串 ""。

示例 1：
輸入：strs = ["flower","flow","flight"]輸出："fl"示例 2：
輸入：strs = ["dog","racecar","car"]輸出：""解釋：輸入不存在公共前綴。

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

二、解題思路

(1) 橫向遍歷法

解題思路：

如下圖所示，依次遍歷字符串數組中的每一個字符串：

具體步驟如下：

• 先計算前兩個元素S1和S2的最長公共前綴LSP(S1,S2)，記為S1

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

• 依次下去，當遍歷完所有的字符串以后，即可得到字符串數組中的最長公共前綴

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

C++實現如下：

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]); //計算兩字符串的最大公共前綴if(!s1.size()) break; //如果沒有公共字符，則最長公共前綴一定是空串}return s1;}//計算兩字符串的最大公共前綴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);}};

測試結果：

復雜度分析；

• 時間復雜度：O(mn)，其中 m 是字符串數組中的字符串的平均長度，n 是字符串的數量。最壞情況下，字符串數組中的每個字符串的每個字符都會被比較一次。

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

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

(2) 縱向遍歷法

解題思路：

如下圖所示，將字符串數組按照如下方式橫向擺布：

具體步驟如下：

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

• 如果不相等，停止遍歷，并返回前i個公共的字符：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();//第一個字符串的長度for(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;}};

測試結果：

復雜度分析

• 時間復雜度：O(nm)，其中 m 是字符串數組中的字符串的平均長度，n 是字符串的數量。

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

以上是“C++如何實現最長公共前綴”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！