Leetcode#14. Longest Common Prefix （最长公共前缀字符串）

xuna小记：题目解法使用c++和Python两种，重点侧重在于解题思路和如何将解法用python语言实现。 同类题目 最长回文字符串：http://blog.csdn.net/xunalove/article/details/77607007

题目

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

题意

找出最长公共前缀字符串

思路

找出长度最短的字符串作为模板字符串，枚举模板字符串的每一个字符，比较所有字符串同一位置是否相同。 例如 str[0] = “1236” ,str[1]=”1348”, str[2]=”12” 模板串：“12” 比较1 :str[0][0]=1,str[1][0]=1,str[2][0]=1 比较2：str[0][1]=2,str[1][1]!=2停止，输出1。

C++代码

class Solution { public: string longestCommonPrefix(vector<string>& strs) { int i,j; string res="",temp; //为空 if(strs.size()==0) return res; //不能再定义时赋值，当strs=""会出现空指针的错误 temp=strs[0]; //找出长度最短的字符串 for(i=1;i<strs.size();i++) { if(temp.size()>strs[i].size()) temp = strs[i]; } //第一层循环为列举每一个字符 for(i=0;i<temp.size();i++) { //同一位置两两比较字符是否相同 for(j=0;j<strs.size();j++) { if(strs[j][i]!=temp[i]) return res; } res+=temp[i]; } return res; } };

Python代码

class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ res ="" if len(strs)==0: return res temp = strs[0] for str in strs: if len(temp) > len(str): temp = str for i in range(0,len(temp)): for j in range(0,len(strs)): if strs[j][i]!=temp[i]: return res; res = res + temp[i] return res;