`
jgsj
  • 浏览: 951505 次
文章分类
社区版块
存档分类
最新评论

LeetCode Longest Common Prefix 最长前缀

阅读更多

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

这是一次性通过的简单问题了。

要点:

1 用第一个string初始化,并初始化当前maxPre为该串长度

2 从第二个string开始比较,并记录当前maxPre的最大长度

3 循环所有vector里面的string

class Solution {
public:
	string longestCommonPrefix(vector<string> &strs) 
	{
		if (strs.empty())
		{
			return string();
		}
		int maxPre = strs[0].length();
		for (int i = 1; i < strs.size(); i++)
		{
			countPrefix(strs[0], maxPre, strs[i]);
		}
		return strs[0].substr(0, maxPre);
	}

	void countPrefix(string &initStr, int &maxPre, string &str)
	{
		int i = 0;
		for (; i < maxPre; i++)
		{
			if (i >= str.length() || initStr[i] != str[i])
			{
				break;
			}
		}
		maxPre = i;
	}
};


2014-1-24 update 更加简洁的程序:

string longestCommonPrefix(vector<string> &strs) 
	{
		string rs;
		if (strs.empty()) return rs;
		int len = strs[0].length();		

		for (int i = 1; i < strs.size(); i++)
		{
			int j = 0;
			for ( ; j<len && j<strs[i].length() && strs[i-1][j]==strs[i][j]; j++);
			len = j;
		}
		return strs[0].substr(0,len);
	}




分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics