14. Longest Common Prefix 最长公共前缀
题目:Roman to Integer 罗马字符转整数
难度:简单
Write 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: "fl"
Example 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
.
题意解析:
写一个方法从一个字符串数组中查找最长的公共前缀,如果没有,返回""
解题思路一:
依次遍历每一个数组项,记录其公共的字符串,最后返回
public String longestCommonPrefix(String[] strs) {
StringBuilder sb = new StringBuilder();
if (strs == null || strs.length == 0){
return "";
}
if (strs[0].length() == 0){
return "";
}else {
for (int i = 0; i < strs[0].length(); i++) {
char temp = strs[0].charAt(i);
int j = 0;
while (j < strs.length){
if (i+1 > strs[j].length()){
return sb.toString();
}
if (strs[j].equals("")){
return "";
}
if (strs[j].charAt(i) == temp){
j++;
}else {
return sb.toString();
}
}
sb.append(temp);
}
}
return sb.toString();
}
此算法时间复杂度O(n²)
提交代码之后:
Runtime: 1 ms, faster than 94.61% of Java online submissions for Longest Common Prefix.
Memory Usage: 39.1 MB, less than 10.90% of Java online submissions for Longest Common Prefix.
解题思路二:
直接取第一个的长度假定为最长的长度,然后依次取数组项中,匹配是否包含这个字符串,如果匹配,直接返回,否则将第一项的长度前移一位,继续匹配。
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0) return "";
String pre = strs[0];
int i = 1;
while(i < strs.length){
while(strs[i].indexOf(pre) != 0)
pre = pre.substring(0,pre.length()-1);
i++;
}
return pre;
}
此算法时间复杂度为
提交代码之后:
Runtime: 0 ms, faster than 100.00% of Java online submissions for Longest Common Prefix.
Memory Usage: 39 MB, less than 15.33% of Java online submissions for Longest Common Prefix.