參考：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?]，當(dāng)遍歷到第 ii 個字符串的時候，找到最長公共前綴 LCP(S_1 \ldots S_i)LCP(S1?…Si?)。
- 當(dāng) LCP(S_1 \ldots S_i)LCP(S1?…Si?) 是一個空串的時候舞终，算法就結(jié)束了。 否則，在執(zhí)行了 nn 次遍歷之后朽基，算法就會返回最終答案 LCP(S_1 \ldots S_n)LCP(S1?…Sn?)。
*復(fù)雜度分析 - 時間復(fù)雜度：O(S)O(S)离陶，S 是所有字符串中字符數(shù)量的總和稼虎。
- 最壞的情況下，nn 個字符串都是相同的招刨。算法會將 S1S1 與其他字符串 [S_2 \ldots S_n][S2?…Sn?] 都做一次比較霎俩。這樣就會進行 SS 次字符比較，其中 SS 是輸入數(shù)據(jù)中所有字符數(shù)量沉眶。
- 空間復(fù)雜度：O(1)O(1)打却，我們只需要使用常數(shù)級別的額外空間。
- @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;
}
/**
- 算法二：水平掃描
- 想象數(shù)組的末尾有一個非常短的字符串谎倔，使用上述方法依舊會進行 S?S? 次比較柳击。優(yōu)化這類情況的一種方法就是水平掃描。我們從前往后枚舉字符串的每一列片习，先比較每個字符串相同列上的字符（即不同字符串相同下標(biāo)的字符）然后再進行對下一列的比較腻暮。
- 復(fù)雜度分析
- 時間復(fù)雜度：O(S)O(S)，S 是所有字符串中字符數(shù)量的總和毯侦。
- 最壞情況下哭靖，輸入數(shù)據(jù)為 nn 個長度為 mm 的相同字符串，算法會進行 S = mnS=m?n 次比較侈离∈杂模可以看到最壞情況下，本算法的效率與算法一相同，但是最好的情況下铺坞，算法只需要進行 nminLenn?minLen 次比較起宽，其中 minLenminLen 是數(shù)組中最短字符串的長度。
- 空間復(fù)雜度：O(1)O(1)济榨，我們只需要使用常數(shù)級別的額外空間坯沪。
- @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];
}
/**
- 算法三：分治
- 算法
- 為了應(yīng)用上述的結(jié)論，我們使用分治的技巧擒滑，將原問題 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 構(gòu)造原問題的解 LCP(S_i \cdots S_j)LCP(Si??Sj?)丐一。 從頭到尾挨個比較 lcpLeft 與 lcpRight 中的字符藻糖，直到不能再匹配為止。 計算所得的 lcpLeft 與 lcpRight 最長公共前綴就是原問題的解 LCP(S_i\cdots S_j)LCP(Si??Sj?)库车。
- 復(fù)雜度分析
- 最壞情況下巨柒，我們有 nn 個長度為 mm 的相同字符串。
- 時間復(fù)雜度：O(S)O(S)柠衍，SS 是所有字符串中字符數(shù)量的總和洋满，S=m*nS=m?n。
- 時間復(fù)雜度的遞推式為 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 是數(shù)組中最短字符串的長度禽最。
- 空間復(fù)雜度：O(m \cdot log(n))O(m?log(n))
- 內(nèi)存開支主要是遞歸過程中使用的棧空間所消耗的袱饭。 一共會進行 log(n)log(n) 次遞歸川无，每次需要 mm 的空間存儲返回結(jié)果，所以空間復(fù)雜度為 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);
}
}
/**
- 算法四：二分查找法
- 這個想法是應(yīng)用二分查找法找到所有字符串的公共前綴的最大長度 L懦趋。 算法的查找區(qū)間是 (0 \ldots minLen)(0…minLen)，其中 minLen 是輸入數(shù)據(jù)中最短的字符串的長度疹味，同時也是答案的最長可能長度仅叫。 每一次將查找區(qū)間一分為二，然后丟棄一定不包含最終答案的那一個糙捺。算法進行的過程中一共會出現(xiàn)兩種可能情況：
- S[1...mid] 不是所有串的公共前綴诫咱。 這表明對于所有的 j > i S[1..j] 也不是公共前綴，于是我們就可以丟棄后半個查找區(qū)間洪灯。
- S[1...mid] 是所有串的公共前綴坎缭。 這表示對于所有的 i < j S[1..i] 都是可行的公共前綴，因為我們要找最長的公共前綴，所以我們可以把前半個查找區(qū)間丟棄掏呼。
- 復(fù)雜度分析
- 最壞情況下坏快，我們有 nn 個長度為 mm 的相同字符串。
- 時間復(fù)雜度：O(S \cdot log(n))O(S?log(n))憎夷，其中 SS 所有字符串中字符數(shù)量的總和莽鸿。
- 算法一共會進行 log(n)log(n) 次迭代，每次一都會進行 S = m*nS=m?n 次比較拾给，所以總時間復(fù)雜度為 O(S \cdot log(n))O(S?log(n))祥得。
- 空間復(fù)雜度：O(1)O(1)，我們只需要使用常數(shù)級別的額外空間鸣戴。
- @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);
}/**
用前綴樹實現(xiàn)
復(fù)雜度分析
*最壞情況下查詢字符串 q的長度為 mm 并且它與數(shù)組中 n個字符串均相同啃沪。時間復(fù)雜度：預(yù)處理過程 O(S)粘拾，其中 S數(shù)組里所有字符串中字符數(shù)量的總和窄锅，最長公共前綴查詢操作的復(fù)雜度為 O(m)。
建立字典樹的時間復(fù)雜度為 O(S)缰雇。在字典樹中查找字符串 qq 的最長公共前綴在最壞情況下需要 O(m) 的時間入偷。
空間復(fù)雜度：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"));
}
}
