` (strs[i].indexOf(prefix) != 0) ` in find LongestCommonPrefix

Question

J'ai lu une telle solution pour LongestCommonPrefix

Préfixe commun le plus long - LeetCode

 public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++)
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}

Quant à while (strs[i].indexOf(prefix) != 0) si prefix n'est pas vide, l'expression retournera constamment True ;

Comment pourrait-on conclure que prefix = prefix.substring(0, prefix.length() - 1); j'ai supposé que le while (strs[i].indexOf(prefix) != 0) n'a rien fait.

Answer 1

L'idée de cet algorithme est la suivante :

1. suppose d'abord que le premier mot est le prefix et nous vérifierons ensuite si prefix est le préfixe de tous les autres mots.

2. si strs[i].indexOf(prefix) != 0 signifie qu'il ne commence pas avec prefix . Nous devrions donc réduire un peu le préfixe (en supprimant le dernier caractère caractère), c'est-à-dire prefix = prefix.substring(0, prefix.length() - 1);

3. nous faisons cela continuellement, util tous les mots vérifiés, ou le préfixe a été coupé à '' (c'est pourquoi il est appelé Horizontal scanning )

J'espère que cela vous aidera, et commentez si vous avez d'autres questions : )

Answer 2

Ce code prend la première chaîne de caractères d'une liste de chaînes de caractères.

String prefix = strs[0];

Et supprime le dernier caractère de cette chaîne

prefix = prefix.substring(0, prefix.length() - 1);

Jusqu'à la prochaine chaîne contient cette sous-chaîne.

while (strs[i].indexOf(prefix) != 0)

Cette opération est répétée pour chaque chaîne du tableau d'entrée.

for (int i = 1; i < strs.length; i++)

Si l'algorithme a vérifié avec succès que strs[i].indexOf(prefix) != 0 pour chaque chaîne d'entrée, prefix est la plus longue sous-chaîne mais pas le plus long préfixe commun.

Comme vous l'avez déjà mentionné dans les commentaires, au lieu de vérifier la présence de strs[i].indexOf(prefix) != 0 vous devez utiliser strs[i].startsWith(prefix) comme condition pour la boucle "while". De cette façon, vous devriez obtenir le commun préfixe .