最长公共前缀

2019-06-19 本文已影响0人 iamlyly

参考：https://leetcode-cn.com/problems/two-sum/solution/zui-chang-gong-gong-qian-zhui-by-leetcode/

/**

最长公共前缀
*/
public class CommonPrefix {
public String longestCommonPrefix(String[] strs) {
if(strs==null||strs.length==0) return "";
String minLengthStr = strs[0];
for(int i=1;i<strs.length-1;i++){
if(strs[i].length()<minLengthStr.length())minLengthStr=strs[i];
}
boolean flag=true;
while(minLengthStr!=""){
for(int n=0;n<strs.length;n++){
String tmp = strs[n];
if(!tmp.startsWith(minLengthStr)){
minLengthStr=minLengthStr.substring(0,minLengthStr.length()-1);
flag=false;
break;
}else {
flag=true;
}
}
if(flag==true) break;
}
if(flag==true){
return minLengthStr;
```
 }else return "";
```
}

/**
- 水平扫描表
- 为了运用这种思想，算法要依次遍历字符串 [S_1 \ldots S_n][S1…Sn]，当遍历到第 ii 个字符串的时候，找到最长公共前缀 LCP(S_1 \ldots S_i)LCP(S1…Si)。
- 当 LCP(S_1 \ldots S_i)LCP(S1…Si) 是一个空串的时候，算法就结束了。否则，在执行了 nn 次遍历之后，算法就会返回最终答案 LCP(S_1 \ldots S_n)LCP(S1…Sn)。
  *复杂度分析
- 时间复杂度：O(S)O(S)，S 是所有字符串中字符数量的总和。
- 最坏的情况下，nn 个字符串都是相同的。算法会将 S1S1 与其他字符串 [S_2 \ldots S_n][S2…Sn] 都做一次比较。这样就会进行 SS 次字符比较，其中 SS 是输入数据中所有字符数量。
- 空间复杂度：O(1)O(1)，我们只需要使用常数级别的额外空间。
- @param strs
- @return
  */
  public String longestCommonPrefix1(String[] strs) {
  if(strs==null||strs.length==0) return "";
  String prefix = strs[0];
  for(int i=1;i<strs.length-1;i++){
  while(strs[i].indexOf(prefix)!=0){
  prefix = prefix.substring(0,prefix.length()-1);
  if(prefix=="") return "";
  }
  }
  return prefix;
  }
/**
- 算法二：水平扫描
- 想象数组的末尾有一个非常短的字符串，使用上述方法依旧会进行 SS 次比较。优化这类情况的一种方法就是水平扫描。我们从前往后枚举字符串的每一列，先比较每个字符串相同列上的字符（即不同字符串相同下标的字符）然后再进行对下一列的比较。
- 复杂度分析
- 时间复杂度：O(S)O(S)，S 是所有字符串中字符数量的总和。
- 最坏情况下，输入数据为 nn 个长度为 mm 的相同字符串，算法会进行 S = mnS=m∗n 次比较。可以看到最坏情况下，本算法的效率与算法一相同，但是最好的情况下，算法只需要进行 nminLenn∗minLen 次比较，其中 minLenminLen 是数组中最短字符串的长度。
- 空间复杂度：O(1)O(1)，我们只需要使用常数级别的额外空间。
- @param strs
- @return
  */
  public String longestCommonPrefix2(String[] strs) {
  if(strs==null||strs.length==0) return "";
  for(int i=0;i<strs[0].length();i++){
  char c = strs[0].charAt(i);
  for(int j=1;j<strs.length;j++){
  if(i==strs[j].length()||strs[j].charAt(i)!=c){
  return strs[0].substring(0,i);
  }
  }
  }
  return strs[0];
  }
/**
- 算法三：分治
- 算法
- 为了应用上述的结论，我们使用分治的技巧，将原问题 LCP(S_i\cdots S_j)LCP(Si⋯Sj) 分成两个子问题 LCP(S_i\cdots S_{mid})LCP(Si⋯Smid) 与 LCP(S_{mid+1}, S_j)LCP(Smid+1,Sj) ，其中 mid = (i+j)/2。我们用子问题的解 lcpLeft 与 lcpRight 构造原问题的解 LCP(S_i \cdots S_j)LCP(Si⋯Sj)。从头到尾挨个比较 lcpLeft 与 lcpRight 中的字符，直到不能再匹配为止。计算所得的 lcpLeft 与 lcpRight 最长公共前缀就是原问题的解 LCP(S_i\cdots S_j)LCP(Si⋯Sj)。
- 复杂度分析
- 最坏情况下，我们有 nn 个长度为 mm 的相同字符串。
- 时间复杂度：O(S)O(S)，SS 是所有字符串中字符数量的总和，S=m*nS=m∗n。
- 时间复杂度的递推式为 T(n)=2\cdot T(\frac{n}{2})+O(m)T(n)=2⋅T(2n)+O(m)，化简后可知其就是 O(S)O(S)。最好情况下，算法会进行 minLen\cdot nminLen⋅n 次比较，其中 minLenminLen 是数组中最短字符串的长度。
- 空间复杂度：O(m \cdot log(n))O(m⋅log(n))
- 内存开支主要是递归过程中使用的栈空间所消耗的。一共会进行 log(n)log(n) 次递归，每次需要 mm 的空间存储返回结果，所以空间复杂度为 O(m\cdot log(n))O(m⋅log(n))。
- @param strs
- @return
  */
  public String longestCommonPrefix3(String[] strs){
  if(strs==null||strs.length==0) return "";
  return this.longestCommonPrefix3(strs,0,strs.length-1);
  }
  public String longestCommonPrefix3(String[] strs,int l ,int r){
  if(strs==null||strs.length==0) return "";
  if(l==r){
  return strs[l];
  }else {
  int mid = (l+r)/2;
  String leftStr = this.longestCommonPrefix3(strs,l,mid);
  String rightStr = this.longestCommonPrefix3(strs,mid+1,r);
  return this.getCommonPrevStr(leftStr,rightStr);
  }
  }
/**
- 算法四：二分查找法
- 这个想法是应用二分查找法找到所有字符串的公共前缀的最大长度 L。算法的查找区间是 (0 \ldots minLen)(0…minLen)，其中 minLen 是输入数据中最短的字符串的长度，同时也是答案的最长可能长度。每一次将查找区间一分为二，然后丢弃一定不包含最终答案的那一个。算法进行的过程中一共会出现两种可能情况：
- S[1...mid] 不是所有串的公共前缀。这表明对于所有的 j > i S[1..j] 也不是公共前缀，于是我们就可以丢弃后半个查找区间。
- S[1...mid] 是所有串的公共前缀。这表示对于所有的 i < j S[1..i] 都是可行的公共前缀，因为我们要找最长的公共前缀，所以我们可以把前半个查找区间丢弃。
- 复杂度分析
- 最坏情况下，我们有 nn 个长度为 mm 的相同字符串。
- 时间复杂度：O(S \cdot log(n))O(S⋅log(n))，其中 SS 所有字符串中字符数量的总和。
- 算法一共会进行 log(n)log(n) 次迭代，每次一都会进行 S = m*nS=m∗n 次比较，所以总时间复杂度为 O(S \cdot log(n))O(S⋅log(n))。
- 空间复杂度：O(1)O(1)，我们只需要使用常数级别的额外空间。
- @param strs
- @return
  */
  public String longestCommonPrefix4(String[] strs){
  if(strs==null||strs.length==0) return "";
  int minLen = Integer.MAX_VALUE;
  for(String str:strs){
  minLen = Math.min(minLen,str.length());
  }
  int low = 1;
  int high = minLen;
  while(low<=high){
  int middle = (low+high)/2;
  if(isCommonPrefix(strs,middle)){
  low = middle+1;
  }else {
  high = middle-1;
  }
  }
  return strs[0].substring(0,(low+high)/2);
  }
  public boolean isCommonPrefix(String[] strs,int len){
  String commonPrefix = strs[0].substring(0,len);
  for(int i=1;i<strs.length;i++){
  if(!strs[i].startsWith(commonPrefix)) return false;
  }
  return true;
  }
public String getCommonPrevStr (String str1,String str2){
int midLen = Math.min(str1.length(),str2.length());
for(int i=0;i<midLen;i++){
if (str1.charAt(i) != str2.charAt(i)) {
return str1.substring(0,i);
}
}
return str1.substring(0,midLen);
}

/**
- 用前缀树实现
- 复杂度分析
  *最坏情况下查询字符串 q的长度为 mm 并且它与数组中 n个字符串均相同。
- 时间复杂度：预处理过程 O(S)，其中 S数组里所有字符串中字符数量的总和，最长公共前缀查询操作的复杂度为 O(m)。
- 建立字典树的时间复杂度为 O(S)。在字典树中查找字符串 qq 的最长公共前缀在最坏情况下需要 O(m) 的时间。
- 空间复杂度：O(S)O(S)，我们只需要使用额外的 SS 空间建立字典树。
- @param strs
- @return
  */
  public String longestCommonPrefix5(String[] strs){
  if(strs==null||strs.length==0) return "";
  Trie trie = new Trie();
  for(int i=1;i<strs.length;i++){
  trie.insert(strs[1]);
  }
  return trie.searchLongestPrefix(strs[0]);
}
public static void main(String[] args){
CommonPrefix commonPrefix= new CommonPrefix();
String[] strs = {"dog","dot","door"};
System.out.println(commonPrefix.longestCommonPrefix5(strs));
}
}

前缀树
public class Trie {
/** Initialize your data structure here. */
private TrieNode root = new TrieNode();

public Trie() {

}

/** Inserts a word into the trie. */
public void insert(String word) {
    char[] chars = word.toCharArray();
    TrieNode cur = root;
    for(char c:chars){
        if(!cur.containsKey(c)){
           TrieNode trieNode= new TrieNode();
           trieNode.setC(c);
            cur.put(c,trieNode);
        }
        cur = cur.get(c);
    }
    cur.setEnd();
}

/** Returns if the word is in the trie. */
public boolean search(String word) {
    char[] chars = word.toCharArray();
    TrieNode cur = root;
    for(char c:chars){
        if(!cur.containsKey(c)){
            return false;
        }
        cur = cur.get(c);
    }
    if(!cur.isEnd) return false;

    return true;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
    char[] chars = prefix.toCharArray();
    TrieNode cur = root;
    for(char c:chars){
        if(!cur.containsKey(c)){
            return false;
        }
        cur = cur.get(c);
    }

    return true;
}
public String searchLongestPrefix(String word) {
    TrieNode cur = root;
    StringBuffer prefix = new StringBuffer();
    for(int i=0;i<word.length();i++){
        char c = word.charAt(i);
        if(cur.containsKey(c)){
            prefix.append(c);
            cur = cur.get(c);
        }else{
            break;
        }
    }
    return prefix.toString();
}

    class TrieNode{
    private static final int n=26;
    private TrieNode[] nexts=new TrieNode[n];
    private int size=0;
    private boolean isEnd;
    private char c;

        public char getC() {
            return c;
        }

        public void setC(char c) {
            this.c = c;
        }

        public boolean isEnd() {
        return isEnd;
    }

    public void setEnd() {
        isEnd = true;
    }

    public void put(char c, TrieNode node){
        nexts[c-'a']=node;
        size++;
    }
    public int getNextsSize(){
        return size;
    }
    public boolean containsKey(char c){
        return nexts[c-'a']!=null?true:false;
    }
    public TrieNode get(char c) {
        return nexts[c - 'a'];
    }
}

public static void main(String[] args){
    Trie obj = new Trie();
 obj.insert("word");
System.out.println(obj.search("word"));
    System.out.println(obj.startsWith("wo"));
}

}

最长公共前缀

猜你喜欢

热点阅读