算法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，附测试结果