Tìm tiền tố chung dài nhất?

Question

Trong hai chuỗi:

"Mary Đã có một con cừu nhỏ"
"Mary Had a Big Chiên Con"

nên trở

"Mary Had a"

Answer 1

Sử dụng tìm kiếm nhị phân. Hãy thử so sánh toàn bộ chuỗi. Nếu họ không bằng nhau hãy thử so sánh các ký tự đầu tiên. Nếu họ bằng nhau cố gắng chia các chuỗi (substring(0, str.length()/2). Vv, v.v.

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

Đây có thể không phải là giải pháp tối ưu, nhưng điều này rất dễ hiểu và lập trình.

Tôi đã mượn ý tưởng này từ danh sách kỹ thuật hợp nhất của thuật toán merge-sort. Nếu bạn đọc ít về kỹ thuật hợp nhất danh sách, bạn sẽ hiểu rõ hơn về logic của thuật toán của tôi.

Answer 3

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

1. a.startsWith (b) == true nếu không
2. trong một vòng lặp tiếp tục xóa char cuối cùng từ str1 và lặp lại kiểm tra của bước 1.

Answer 4

Bạn không cần sử dụng một số StringBuilder - chỉ cần trả về chuỗi con:

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

Giải pháp này áp dụng cho nhiều bước ng mảng. Khi bạn có 3 hoặc 4 chuỗi, tốt hơn là sử dụng StringBuilder. Đối với 2 chuỗi, nó là ok để sử dụng chuỗi con. Mã trong 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(); 
}