查找最長共同前綴？

Question

在兩個字符串：

「瑪麗有隻小羊羔」
「瑪麗有一個大的羔羊」

應該返回

「瑪麗有隻」

Answer 1

使用二進制搜索。嘗試比較整個字符串。如果他們不相同，嘗試比較第一個字符。如果他們是平等的嘗試拆分字符串（substring(0, str.length()/2）。等等

Answer 2

public class Test{ 
public static void main(String[] args){ 
    String s1 = "Mary Had a Little Lamb"; 
    String s2 = "Mary Had a Big Lamb"; 
    int minStrLen = s1.length(); 
    if (minStrLen > s2.length()){ 
     minStrLen = s2.length(); 
    } 

    StringBuilder output = new StringBuilder(); 
    for(int i=0; i<minStrLen; i++){ 
     if (s1.charAt(i) == s2.charAt(i)){ 
     output.append(s1.charAt(i)); 
     }else{ 
      break; 
     } 
    }  
    System.out.println(output.toString()); 
    } 
} 

這可能不是最佳的解決方案，但這很容易理解和編程。

我借用了merge-sort算法列表合併技術的這個思路。如果你對列表合併技術閱讀不多，你會更好地理解我的算法的邏輯。

Answer 3

String str1; 
String str2; 
// assuming str1.length > str2.length 

1. a.startsWith（二）==真 如果不是
2. 在一個循環中保持從步驟str1和重複檢查刪除最後一個字符1.

Answer 4

你不需要使用StringBuilder - 只返回字符串：

public String greatestCommonPrefix(String a, String b) { 
    int minLength = Math.min(a.length(), b.length()); 
    for (int i = 0; i < minLength; i++) { 
     if (a.charAt(i) != b.charAt(i)) { 
      return a.substring(0, i); 
     } 
    } 
    return a.substring(0, minLength); 
} 

Answer 5

該解決方案適用於多種STRI ng數組。當你有3或4個字符串時，最好使用StringBuilder。對於2個字符串，可以使用子字符串。在C＃中的代碼：

public string LongestCommonPrefix(string[] strs) { 
    if(strs.Length == 0) return string.Empty; 

    Array.Sort(strs); 

    var first = strs[0]; 
    var last = strs[strs.Length - 1]; 

    var sb = new StringBuilder(); 
    for(int i = 0; i< first.Length; i++) 
    { 
     if(first[i] != last[i]) 
     { 
      break; 
     } 
     sb.Append(first[i]); 
    } 

    return sb.ToString(); 
}