描述

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

思路

这题是找一个字符串数组的最长公共前缀子序列的。我的思路是先找到最短序列的长度，依次遍历，利用数组记录第j个字符串第i个字符出现的次数，如果第i个字符在所有字符串中都出现，将该字符串拼接到longestCommonPrefix上，如果第i个字符并不在所有字符串中都出现，此时并返回结果。

代码

class Solution { public: string longestCommonPrefix(vector<string>& strs) { if(strs.size() == 0) return ""; int min_length = 99999; int char_map[128] = {0}; int j; char ch; string longestCommonPrefix; for(int i = 0; i < strs.size(); i++){ min_length = min_length > strs[i].size()? strs[i].size():min_length; } for(int i = 0; i < min_length; i++){ for(j = 0; j < strs.size(); j++){ ch = strs[j][i]; if(char_map[ch]==j){ char_map[ch]++; } else{ break; } } if(char_map[ch] == strs.size()){ longestCommonPrefix += ch; char_map[ch] = 0; } else{ break; } } return longestCommonPrefix; } };

结果

他山之玉

C++ O(n) solutioin

class Solution { public: string longestCommonPrefix(vector<string>& strs) { int num= strs.size(), len=INT_MAX; for(int i=0;i<num;i++) if (strs[i].size()<len) len=strs[i].size();// find out the minimum length among the strings if (num==0 || len==0) return ""; for(int i=0;i<len;i++) for(int j=1;j<num;j++) if (strs[j][i]!=strs[j-1][i]) return strs[j].substr(0,i);// find the longest return strs[0].substr(0,len);// the answer is one of the strings } };

这个code的解题思路跟我的思路一样，只是编程的方式更简洁一点，没有用hash的思想，而是直接前后字符串对比，返回子串。

Java O(n) solution

public String longestCommonPrefix(String[] strs) { StringBuilder result = new StringBuilder(); if (strs!= null && strs.length > 0){ Arrays.sort(strs); char [] a = strs[0].toCharArray(); char [] b = strs[strs.length-1].toCharArray(); for (int i = 0; i < a.length; i ++){ if (b.length > i && b[i] == a[i]){ result.append(b[i]); } else { return result.toString(); } } return result.toString(); }

这个人的思路很有意思，先将数组排序，然后检查排序好的数组的第一个跟最后一个字符串 python O(n) solution

class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ return ''.join(['#']+[[' ',p[0]][len(set(p))==1] for p in zip(*strs)]).split()[0][1:]

这个厉害了，python 一行解决，思路是利用zip函数，把这些数组对应起来，检查每一个对应的数组中是不是只有一个字符。