参考：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"));
}
}
