Leetcode 細節實現 Longest Common Prefix

Leetcode 細節實現 Longest Common Prefix

Longest Common Prefix

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

題意：在一個字符串數組中找到最長的公共前綴
思路：
掃描數組，直到遇到一個在各個字符串不一樣的字符
復雜度：時間O(n1 + n2 + ...) --> 最差的情況下，每個字符串都要掃描一遍，空間O(1)

string longestCommonPrefix(vector &strs){
	if(strs.size() == 0) return "";
	if(strs.size() == 1) return strs[0];
	int c = 0;
	while(1){
		for(int i = 1; i < strs.size(); ++i){
			if(strs[i].size() <= c || strs[0].size() <= c || strs[i][c] != strs[0][c]) return strs[0].substr(0, c);
		}
		c++;
	}
}