面试经典150题——最长公共前缀

面试经典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;
    }
}