Trova il prefisso comune più lungo?

Question

In due stringhe:

"Mary aveva un agnellino"
"Maria ha avuto un grande Agnello"

dovrebbe restituire

"Mary Had a"

Answer 1

Utilizzare la ricerca binaria. Prova a confrontare intere stringhe. Se non sono uguali prova a confrontare i primi caratteri. Se sono uguali prova a dividere le stringhe (substring(0, str.length()/2). Ecc, ecc.

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

Questa potrebbe non essere la soluzione ottimale, ma è facile da capire e programmare.

Ho preso in prestito questa idea dalla tecnica di fusione dell'elenco dell'algoritmo merge-sort. Se leggi poco sulla tecnica di fusione delle liste, capirai meglio la logica del mio algoritmo.

Answer 3

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

1. a.startsWith (b) == true se non
2. in un ciclo mantenere l'eliminazione dell'ultimo carattere da str1 e ripetere verifica della fase 1.

Answer 4

Non lo sai necessario utilizzare un StringBuilder - basta restituire la stringa:

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

Questa soluzione applicata ad un multiplo stri ng array. Quando hai 3 o 4 stringhe, è meglio usare StringBuilder. Per 2 stringhe, è ok usare la sottostringa. Codice in 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(); 
}