[LeetCode] 14. Longest Common Prefix

题目

14. Longest Common Prefix

描述

求一个字符串数组的最长公共前缀字符串。

思路

我记得这个题是得用动态规划算法才能有比较优的解法，但貌似比较复杂，我暂时用朴素算法求解了。

class Solution {
public:
	string longestCommonPrefix(vector<string>& strs){
		if(strs.size()==0) return string();

		//find the shortest one
		size_t len = strs[0].size();
		for(size_t i=1; i<strs.size(); i++){
			if(strs[i].size() < len){
				len = strs[i].size();
			}
		}

		// find common prefix
		size_t n = 0;
		while(n < len){
			size_t sz = strs.size();
			char ch = strs[0][n];
			size_t i;
			for(i=1; i<sz; i++){
				if(strs[i][n] != ch){
					break;
				}
			}

			if(i == sz){ // all equal
				n++;
			}
			else{
				break;
			}
		}

		return string(strs[0].c_str(), n);
	}
};