¿Busca el prefijo común más largo?

Question

En dos cadenas:

"Mary Had a Little Lamb"
"Maria tenía un Big Cordero"

debe devolver

"Mary Had a"

Answer 1

Usar la búsqueda binaria. Intenta comparar cadenas enteras. Si no son iguales, intente comparar los primeros caracteres. Si son iguales, intente dividir las cadenas (substring(0, str.length()/2). Etc, etc.

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

Puede que esta no sea la solución óptima, pero es fácil de entender y programar.

Tomé prestada esta idea de la técnica de fusión de listas del algoritmo merge-sort. Si lees poco sobre la técnica de combinación de listas, entenderás mejor la lógica de mi algoritmo.

Answer 3

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

1. a.startsWith (b) == true si no
2. en un bucle de mantener la supresión de la última carbón de str1 y repita la comprobación del paso 1.

Answer 4

Usted no lo hace necesitará utilizar un StringBuilder - acaba de regresar la subcadena:

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

Esta solución se aplica a un múltiplo de STRI ng array. Cuando tienes 3 o 4 cadenas, es mejor usar StringBuilder. Para 2 cadenas, está bien usar subcadena. Código en 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(); 
}