Préfixe commun le plus long pour n string

Pourquoi utiliser Trie (qui prend l'espace O (MN) Time and O (mn), utilisez simplement la force de force brute de base. Première boucle, trouvez la chaîne la plus courte en tant que MINSTR, qui prend O (n) temps, deuxième boucle , Comparez-en une à une avec ce Mintr, et conservez une variable qui indique l'indice le plus à droite de Mintr, cette boucle prend o (mn) où M est la longueur la plus courte de toutes les chaînes. Le code est comme ci-dessous,

public String longestCommonPrefix(String[] strs) {
    if(strs.length==0) return "";
    String minStr=strs[0];

    for(int i=1;i<strs.length;i++){
        if(strs[i].length()<minStr.length())
            minStr=strs[i];
    }
    int end=minStr.length();
    for(int i=0;i<strs.length;i++){
        int j;
        for( j=0;j<end;j++){
            if(minStr.charAt(j)!=strs[i].charAt(j))
                break;
        }
        if(j<end)
            end=j;
    }
    return minStr.substring(0,end);
}

public String longestCommonPrefix(String[] strs) {

    if (strs == null || strs.length == 0)
        return "";

    char[] c_list = strs[0].toCharArray();
    int len = c_list.length;
    int j = 0;
    for (int i = 1; i < strs.length; i++) {
        for (j = 0; j < len && j < strs[i].length(); j++) 
           if (c_list[j] != strs[i].charAt(j)) 
            break;
        len = j;
    }

    return new String(c_list).substring(0, len);

}

Il arrive que le type de seau (Tri radix) décrit par Corsika puisse être étendu de manière à ce que toutes les cordes soient finalement placées seules dans un seau et à ce stade, le LCP pour une chaîne aussi solitaire est connue. En outre, l'intrigant de chaque chaîne est également connue; C'est un plus long que le LCP. Le type de godet est défacto la construction d'un ensemble de suffixe, mais seulement partiellement. Ces comparaisons qui ne sont pas effectuées (comme décrit par CORIKA) représentent en effet ces parties des chaînes suffixes qui ne sont pas ajoutées à la matrice suffixe. Enfin, cette méthode permet de déterminer non seulement le LCP et les diffuseurs, mais également on peut facilement trouver ces sous-séquences qui ne sont pas présentes dans la chaîne.

Puisque le monde mendie évidemment pour une réponse à Swift, voici la mienne;) xxx pré>

SWIFT 3 mise à jour: strong> p> xxx

Qu'est-ce qui est intéressant à noter: p>

1. ceci fonctionne dans o ^ 2, ou o (n x m) où n est le nombre de cordes et m est la longueur du plus court. li>
2. Ceci utilise le type de données String.index et traite donc des clusters code> code> que le type le type code> représente. li> ol>

   et donné la fonction que je devais écrire en premier lieu: p> xxx pré>

   Voici un test d'unité minimal: P>

   func testReifySimple() {
       let samplePaths:[String] = [
           "/root/some/file"
       ,   "/root/some/other/file"
       ,   "/root/another/file"
       ,   "/root/direct.file"
       ]
   
       let expectedPaths:[String] = [
           "some/file"
       ,   "some/other/file"
       ,   "another/file"
       ,   "direct.file"
       ]
   
       let reified = PathUtilities().reify(samplePaths)
   
       for (index, expected) in expectedPaths.enumerate(){
           XCTAssert(expected == reified[index], "failed match, \(expected) != \(reified[index])")
       }
   }
   

Peut-être une solution plus intuitive. Channel le préfixe déjà trouvé hors de l'itération antérieure en tant que chaîne d'entrée sur l'entrée de chaîne restante ou suivante. [[[[W1, W2], W3], W4] ... Donc] Code>, où [] code> est supposément le LCP de deux cordes.

public String findPrefixBetweenTwo(String A, String B){
    String ans = "";
    for (int i = 0, j = 0; i < A.length() && j < B.length(); i++, j++){
        if (A.charAt(i) != B.charAt(j)){
            return i > 0 ? A.substring(0, i) : "";
        }
    }
    // Either of the string is prefix of another one OR they are same.
    return (A.length() > B.length()) ?  B.substring(0, B.length()) : A.substring(0, A.length());
}
public String longestCommonPrefix(ArrayList<String> A) {
    if (A.size() == 1) return A.get(0);

    String prefix = A.get(0);
    for (int i = 1; i < A.size(); i++){
        prefix = findPrefixBetweenTwo(prefix, A.get(i)); // chain the earlier prefix 
    }
    return prefix;
}