DescriptionWrite a function to find the longest common prefix string amongst an array of strings.If there is no common prefix, return an empty string “”.Example 1:Input: [flower,flow,flight] Output: flExample 2:Input: [dog,racecar,car] Output: Explanation: There is no common prefix among the input strings.Note:All given inputs are in lowercase letters a-z.分析题目的意思是找出字符串数组的最长公共前缀。先对字符串进行排序这样差距最大的两个字符串必定是排在第一排和最后一排我们只需要判断第一排和最后一排饿最长公共字符串就行了。C 代码//先对字符串排序然后考虑第一个和最后一个的首字符这两个字符必定是差距最大的两个 //(因为排序首先从第一个开始排)如果这两个不等就返回空否则说明所有字符串的首 //字符相等那么接着判断第二个。 class Solution { public: string longestCommonPrefix(vectorstring strs) { if(strs.size()0){ return ; } sort(strs.begin(),strs.end()); int lenstrs.size(); int lmin(strs[0].size(),strs[len-1].size()); for(int i0;il;i){ if(strs[0][i]!strs[len-1][i]){ return strs[0].substr(0,i); } } return strs[0]; } };Python 代码排序的方法class Solution: def longestCommonPrefix(self, strs: List[str]) - str: strs.sort() first strs[0] last strs[-1] i 0 while ilen(first) and i len(last) and first[i]last[i]: i1 return first[:i]还有一个比较笨的方法就是下面的所有的字符串都跟第一个字符串进行比较没有用排序的方法思路比较直接。class Solution: def longestCommonPrefix(self, strs: List[str]) - str: i0 flagFalse while ilen(strs[0]): for s in strs[1:]: if ilen(s) or ilen(strs[0]) or strs[0][i]!s[i]: flagTrue break if flag: break i1 return strs[0][:i]下面是一个简洁一点的版本class Solution: def longestCommonPrefix(self, strs: List[str]) - str: n len(strs[0]) cnt len(strs) for i in range(n): ch strs[0][i] for j in range(1,cnt): if i len(strs[j]) or strs[j][i]!ch: return strs[0][:i] return strs[0]参考文献[编程题]longest-common-prefix[LeetCode] Longest Common Prefix 最长共同前缀