Znajdź najdłuższy wspólny przedrostek?

Question

W dwóch ciągów:

"Mary Had a Little Lamb"
"Mary miał duży Lamb"

powinna powrócić

"Mary Had a"

Answer 1

Użyj wyszukiwania binarnego. Spróbuj porównać całe ciągi. Jeśli nie są równe, spróbuj porównać pierwsze znaki. Jeśli są równe, spróbuj rozdzielić struny (substring(0, str.length()/2). Itp itd.

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

To może nie być optymalne rozwiązanie, ale jest łatwe do zrozumienia i zaprogramowania.

Pożyczyłem ten pomysł z algorytmu scalania listy algorytmu merge-sort. Jeśli przeczytasz trochę o technikach łączenia list, lepiej zrozumiesz logikę mojego algorytmu.

Answer 3

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

1. a.startsWith (b) == true jeśli nie
2. w pętli zachować usuwając ostatnią char z str1 i powtórnej kontroli w punkcie 1.

Answer 4

nie robić trzeba użyć StringBuilder - wystarczy zwrócić podciąg:

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

to rozwiązanie zastosowane do wielu stri ng tablica. Kiedy masz 3 lub 4 ciągi, lepiej użyć StringBuilder. W przypadku 2 ciągów można używać podciągu. Kod w języku 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(); 
}