Je voudrais savoir si une sous-chaîne est dans une chaîne sans utiliser les méthodes Javascript intégrées de includes , indexOf , (toute similaire à celles-ci), ou des expressions régulières. Je cherche essentiellement à apprendre une approche algorithmique.
C'est ce que j'ai jusqu'à présent
function isSubstring(string, substring){
substringIndex = 0;
// loop through string
for(let i = 0; i< string.length; i++){
//check the current substring index if it matches
if(string[i] === substring[substringIndex]){
substringIndex++
//continue searching... Would i then have to call another function recursively?
}
}
}
J'ai du mal à comprendre comment construire l'algorithme. Une fois qu'il trouve ce premier caractère qui correspond, je voudrais simplement passer au suivant et s'il correspond, continuer à l'index suivant de la chaîne? Aurais-je alors besoin d'une fonction récursive distincte de la boucle que je fais actuellement? J'essaie de m'améliorer dans la pensée algorithmique. Merci.
5 Réponses :
De nombreuses approches sont possibles. En voici une: Créez une fonction plus simple qui vérifiera si une première chaîne est à la position concrète spécifiée, appelons-la start , dans un seconde chaîne. C'est assez simple: vous comparez premier [i] avec deuxième [start + i] pour tous les i dans la plage 0 à la longueur de premier - 1.
Ensuite, la deuxième étape sera de répéter cette fonction pour toutes les positions de début de 0 à la longueur de la deuxième chaîne, tout en vérifiant les limites (vous ne pouvez pas lire après la fin d'une chaîne).
Vous pouvez également faire quelques optimisations plus tard, lorsque la première version fonctionnera. :-)
Par start faites-vous référence à l'index de départ où se trouve ce premier caractère de la sous-chaîne dans l'index?
@nrvaller oui. J'essaye de mettre à jour le texte pour le rendre plus clair.
À chaque itération sur la longueur de la botte de foin, utilisez slice pour extraire les caractères de cet index vers (l'index plus la longueur de l'aiguille). Si la chaîne tranchée correspond à l'aiguille, renvoie true:
function isSubstring(string, substring) {
for (let i = 0; i < string.length; i++) {
const sliced = string.slice(i, i + substring.length);
if (sliced === substring) {
return true;
}
}
return false;
}
console.log(isSubstring('foobar', 'oob'));
console.log(isSubstring('foobar', 'baz'));
Voici un exemple optimisé de l'algorithme isSubstring. Il ne parcourt que le nombre minimum de caractères requis.
Par exemple, si la chaîne comporte 20 caractères et que la sous-chaîne ne comporte que 5 caractères, lorsque nous arrivons à la 16e position de la chaîne, nous pouvons supposer que la sous-chaîne n'existe pas dans la chaîne (16 + 5 = 21> 20)
function isSubstring(str, sub){
if(sub.length > str.length) return false;
for(let i = 0; i < str.length - sub.length + 1; i++){
if(str[i] !== sub[0]) continue;
let exists = true;
for(let j = 1; j < sub.length && exists; j++){
if(str[i+j] === sub[j]) continue;
exists = false;
}
if(exists) return true;
}
return false;
}
//expected true
console.log(isSubstring("hello world", "hello"));
console.log(isSubstring("hello world", "world"));
console.log(isSubstring("hello world", "d"));
console.log(isSubstring("hello world", "o w"));
console.log(isSubstring("hello world", "rl"));
console.log(isSubstring("hello world", ""));
//expected false
console.log(isSubstring("hello world", "hello world 1"));
console.log(isSubstring("hello world", "helloo"));
Vous n'avez pas besoin du if (sub.length> str.length) return false; ; le externe pour -loop n'entrera jamais dans son corps à moins que 0 if (str [i]! == sub [0]) continue; , la boucle interne pour -loop peut commencer à j = 0 < / code>. Enfin, vous pourriez être intéressé par developer.mozilla.org / fr-FR / docs / Web / JavaScript / Reference /… , ce qui peut rendre cela plus facile à lire que votre variable existe .
Puisque vous avez exprimé votre intérêt pour une méthode récursive, voici quelque chose à considérer. En cliquant sur les parties de démarques jaunes, vous découvrez les spoilers.
}
renvoie vrai;
return f(str, sub,
return false;
if (str[i] == sub[j])
return f(str, sub,
i + 1, j + 1);
if (i == str.length)
i + 1, 0);
function f(str, sub, i=0, j=0){
if (j && j == sub.length)
function isSubstring(str, sub) {
return str.split(sub).length > 1
}
No includes, no .indexOf, no RegExp. Just strings.
vous pouvez jeter un oeil à l'implémentation de
indexOf ()ici (sous la légende polyfill).De plus, si vous apprenez et êtes intéressé par la complexité algorithmique, vous voudrez peut-être jeter un coup d'œil sur Algorithme KMP .
L'utilisation de la récursivité fonctionnerait mais limiterait inutilement votre fonction de comparaison aux chaînes qui s'inscrivent dans la pile d'appels. Vous encourriez également beaucoup de frais généraux.