当前位置:首页 » C语言&C++

LeetCode-14-longest-common-prefix

2017-12-18 13:00 本站整理 浏览(5)

一、问题描述

给定一个vector<string>,求出vector中所有字符串的最大公共前缀

例子:

vector<string> v;
v.push_back("124d22e2");
v.push_back("124d2fw");
v.push_back("124d2ggg");
cout << longestCommonPrefix(v) << endl;

对于以上v,输出结果为"124d2"

二、解决思想

令result等于第一个字符串,拿result和后面的所有字符串比较,将result截取为result和字符串相同的前缀部分,便利一遍,即可得到结果。

三、实现代码

string longestCommonPrefix(vector<string>& strs) {
	if (strs.empty())
		return "";
	string result = strs.at(0);
	if (result == "")
		return "";
	for (int i = 1; i < strs.size(); i++) {
		int j = 0;
		string str = strs.at(i);
		while (j < result.size() && j < str.size() && result.at(j) == str.at(j))
			j++;
		result = str.substr(0,j);
	}
	return result;
}

测试代码

int main()
{
	vector<string> v;
	v.push_back("124d22e2");
	v.push_back("124d2fw");
	v.push_back("124d2ggg");
	cout << longestCommonPrefix(v) << endl;

	system("pause");
    return 0;
}