LeetCode刷题实战14: 最长公共前缀
程序IT圈
共 950字,需浏览 2分钟
·
2020-08-19 18:08
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做最长公共前缀 ,我们先来看题面:
https://leetcode-cn.com/problems/longest-common-prefix/
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 "".
题意
""
。样例
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
题解
解法一
首先找出长度最短的字符串str,加入str="abcf"。
依次对'abcf'、'abc'、'ab'、'a'进行筛选,判断哪个是所有其他字符串的前缀。
public String longestCommontPrefix6(String[] strs) {
if(strs.length == 0) {
return "";
}
int min = Integer.MAX_VALUE;
for(String str : strs) {
min = Math.min(min, str.length());
}
int low = 1;
int high = min;
while(low <= high) {
int middle = (low + high)/2;
if(this.isCommontPrefix(strs, middle)) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return strs[0].substring(0, (low + high)/2);
}
public boolean isCommontPrefix(String[] strs, int length) {
String tmp = strs[0].substring(0, length);
for (int i=0; iif(!strs[i].startsWith(tmp)) {
return false;
}
}
return true;
}
解法二
public String longestCommonPrefix3(String[] strs) {
if(strs.length == 0) {
return "";
}
String result = strs[0];
for(int i=0; iwhile(strs[i].indexOf(result) != 0) {
result = result.substring(0, result.length()-1);
if(result.length() == 0) {
return "";
}
}
}
return result;
}
解法三
找出最短的字符串记为m;
对字符串m进行二分,分割点记为mid,用tmp表示m[low...high]。
如果tmp为所有字符串的前缀,则mid右移,否则左移,直到low>high。
代码如下:
public String longestCommontPrefix6(String[] strs) {
if(strs.length == 0) {
return "";
}
int min = Integer.MAX_VALUE;
for(String str : strs) {
min = Math.min(min, str.length());
}
int low = 1;
int high = min;
while(low <= high) {
int middle = (low + high)/2;
if(this.isCommontPrefix(strs, middle)) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return strs[0].substring(0, (low + high)/2);
}
public boolean isCommontPrefix(String[] strs, int length) {
String tmp = strs[0].substring(0, length);
for (int i=0; iif(!strs[i].startsWith(tmp)) {
return false;
}
}
return true;
}
今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。
上期推文:
评论