题目
查找字符串数组中的最长公共前缀, 如果不存在公共前缀,返回空字符串 “”.
示例 1:
输入: [“flower”,”flow”,”flight”]
输出: “fl”
示例 2:
输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。
说明: 所有输入只包含小写字母 a-z
。
我的思路
- 取出第一个字符串换成参照字符数组
- 循环参考字符数组的每一个字符
- 对比相同 不相等返回 相等拼接继续循环
我的代码
执行用时 :1 ms, 在所有 java 提交中击败了87.85%的用户
内存消耗 :37.6 MB, 在所有 java 提交中击败了73.80%的用户
private static String longestCommonPrefix(String[] strs) {
StringBuilder res = new StringBuilder();
if (strs.length <= 0) {
return "";
}
char[] chars = strs[0].toCharArray();
for (int i = 0; i < chars.length; i++) {
char b = chars[i];
for (int j = 1; j < strs.length; j++) {
String s = strs[j];
if (s.length() <= i || s.charAt(i) != b) {
b = 0;
return res.toString();
}
}
res.append(b);
}
return res.toString();
}
提供多种思路
1、所求的最长公共前缀子串一定是每个字符串的前缀子串。所以随便选择一个字符串作为标准,把它的前缀串,与其他所有字符串进行判断,看是否是它们所有人的前缀子串。这里的时间性能是O(m*n*m)。
2、列出所有的字符串的前缀子串,将它们合并后排序,找出其中个数为n且最长的子串。时间性能为O(n*m+m*n*log(m*n))
3、纵向扫描:从下标0开始,判断每一个字符串的下标0,判断是否全部相同。直到遇到不全部相同的下标。时间性能为O(n*m)。
4、横向扫描:前两个字符串找公共子串,将其结果和第三个字符串找公共子串……直到最后一个串。时间性能为O(n*m)。
5、借助trie字典树。将这些字符串存储到trie树中。那么trie树的第一个分叉口之前的单分支树的就是所求。
*(多种写法往后补上)
C 语言代码
4ms
char* longestCommonPrefix(char** strs, int strsSize) {
char* str=(char*)malloc(128);
memset(str,0,128);
int i,j=0;
if(strsSize<=1)
return *(strs);
while(1)
{
i=0;
while(i<strsSize-1)
{
if(strs[i][j]!=strs[i+1][j])
return str;
i++;
}
str[j]=strs[0][j];
j++;
}
return str;
}
python 代码
python两种让你拍大腿的解法,时间复杂度你想象不到,短小精悍。 1、利用python的max()和min(),在Python里字符串是可以比较的,按照ascII值排,举例abb, aba,abac,最大为abb,最小为aba。所以只需要比较最大最小的公共前缀就是整个数组的公共前缀
def longestCommonPrefix(self, strs):
if not strs: return ""
s1 = min(strs)
s2 = max(strs)
for i,x in enumerate(s1):
if x != s2[i]:
return s2[:i]
return s1