查找最长共同前缀？

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(); 
}