面试经典150题 day20
- 题目来源
- 我的题解
- 方法一 横向遍历
- 方法二 纵向遍历
- 方法三 分治
- 方法四 字典树
题目来源
力扣每日一题;题序:14
我的题解
方法一 横向遍历
两两字符串找最长公共前缀
时间复杂度:O(nL)。n表示数组的长度,L表示来两两字符创的最长公共前缀。
空间复杂度:O(1)
public String longestCommonPrefix(String[] strs) {
String pre=strs[0];
for(int i=1;i<strs.length;i++){
pre=pairPrefix(pre,strs[i]);
}
return pre;
}
public String pairPrefix(String s1,String s2){
int i=0;
while(i<s1.length()&&i<s2.length()&&s1.charAt(i)==s2.charAt(i)) i++;
return s1.substring(0,i);
}
方法二 纵向遍历
每次判断当前列的 所有字符是否相同
时间复杂度:O(nL)
空间复杂度:O(1)
public String longestCommonPrefix(String[] strs) {
int i=0;
for(;i<strs[0].length();i++){
if(!isPrefixCol(strs,i)){
return strs[0].substring(0,i);
}
}
return strs[0].substring(0,i);
}
public boolean isPrefixCol(String[] strs,int index){
if(index>=strs[0].length())
return false;
char c=strs[0].charAt(index);
for(int i=1;i<strs.length;i++){
if(index>=strs[i].length())
return false;
if(c!=strs[i].charAt(index))
return false;
}
return true;
}
方法三 分治
方法一的优化版本,可以采用分治的思想,找部分的数组的最长公共前缀,然后再找组合起来的最长公共前缀。
时间复杂度:O(nL)
空间复杂度:O(1)
public String longestCommonPrefix(String[] strs) {
int n=strs.length;
if(n==1)
return strs[0];
return getLongPrefix(strs,0,n-1);
}
public String getLongPrefix(String[] strs,int start,int end){
if(start>end)
return "";
if(start==end)
return strs[start];
int mid=((end-start)>>1)+start;
String left=getLongPrefix(strs,start,mid);
String right=getLongPrefix(strs,mid+1,end);
return pairPrefix(left,right);
}
public String pairPrefix(String s1,String s2){
int i=0;
while(i<s1.length()&&i<s2.length()&&s1.charAt(i)==s2.charAt(i)) i++;
return s1.substring(0,i);
}
方法四 字典树
使用所有字符串构建字典树(也叫前缀树),然后在字典树中找到最短的结束位置。
public String longestCommonPrefix(String[] strs) {
int n=strs.length;
if(n==1)
return strs[0];
//构建字典树并记录最短字符串
DictTree t=new DictTree();
int min=Integer.MAX_VALUE;
int index=0;
for(int i=0;i<n;i++){
t.insert(strs[i]);
if(min>strs[i].length()){
min=strs[i].length();
index=i;
}
}
int end=0;
//在最短字符串中查找最长公共前缀
for(;end<strs[index].length();end++){
if(t.count!=1)
break;
int chIndex=strs[index].charAt(end)-'a';
t=t.next[chIndex];
}
return strs[index].substring(0,end);
}
class DictTree{
boolean isEnd;
DictTree[] next;
int count;//用于记录某一列是否只有一个字符
public DictTree(){
isEnd=false;
next=new DictTree[26];
count=0;
}
// 插入字符串word
public void insert(String word){
DictTree cur=this;
int n=word.length();
for(int i=0;i<n;i++){
int chIndex=word.charAt(i)-'a';
if(cur.next[chIndex]==null){
cur.next[chIndex]=new DictTree();
cur.count++;
}
cur=cur.next[chIndex];
}
cur.isEnd=true;
}
// 查找 word是否在字典树中
public boolean search(String word){
DictTree t=searchPrefix(word);
return t!=null&&t.isEnd;
}
// 判断是否有 prefix为前缀的字符串
public boolean startWithPrefix(String prefix){
return searchPrefix(prefix)!=null;
}
// 查找前缀 prefix的结尾节点
public DictTree searchPrefix(String prefix){
DictTree cur=this;
for(int i=0;i<prefix.length();i++){
int chIndex=prefix.charAt(i)-'a';
if(cur.next[chIndex]==null)
return null;
cur=cur.next[chIndex];
}
return cur;
}
}
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~