算法6：返回一組字符串的最長公共前綴

2019-11-06 06:33:09

字體：大中小

來源：轉載

供稿：網友

問題描述

返回一組字符串的最長公共前綴，如 “abc”, “abcdef”, “abcd”, 則返回”abc”。

解題思路

首先最長公共前綴肯定小于或者等于最短字符串，設第一個字符串為公共字符串，公共字符串長度為第一個字符串的長度，遍歷其他公共字符串，如果其他公共字符串比第一個字符串短，則公共字符串取較短的長度，如果其他字符串的字符不等于第一個字符串的字符，則退出比較，從而得當當前結果的公共字符串，以此類推，直至遍歷除第一個字符串的其他字符串。

c++代碼

string GetCommonPRefix(vector<string>& strs){ string commonStr = ""; int commonStrLen = 0; if(strs.size() <= 1) { return ""; } //設第一個字符串就是公共字符串 commonStr = strs[0]; commonStrLen = commonStr.length(); for (int i = 1; i < strs.size(); i++) { if(commonStrLen > strs[i].length()) { commonStrLen = strs[i].length(); } for(int j = 0; j < commonStrLen; j++) { if(commonStr[j] != strs[i][j]) { commonStrLen = j; break; } } commonStr = strs[i].substr(0,commonStrLen); } return commonStr;}

測試代碼

int _tmain(int argc, _TCHAR* argv[]){ vector<string> strs; strs.clear(); cout<<"please input 6 string:"<<endl; string temp; for(int i = 0; i < 6; i++) { cin>>temp; strs.push_back(temp); } string commonStr = GetCommonPrefix(strs); cout<<"common prefix string is "<<commonStr<<endl; return 0;}

上一篇：Call to undefined function pg_connect()

下一篇：多線程異常捕獲問題：棄用Thread，改用FutureTask，附測試結果