Correspondance de chaînes dans un tableau

1408. Correspondance de chaînes dans un tableau

Difficulté :Facile

Sujets : Tableau, chaîne, correspondance de chaînes

Étant donné un tableau de mots de chaîne, renvoie toutes les chaînes de mots qui sont une sous-chaîne d'un autre mot. Vous pouvez renvoyer la réponse dans n'importe quel ordre.

Une sous-chaîne est une séquence contiguë de caractères au sein d'une chaîne

Exemple 1 :

• Entrée : mots = ["masse","comme","héros","super-héros"]
• Sortie : ["as","hero"]
• Explication : "as" est une sous-chaîne de "masse" et "héros" est une sous-chaîne de "super-héros". ["hero","as"] est également une réponse valable.

Exemple 2 :

• Saisie : mots = ["leetcode","et","code"]
• Sortie : ["et","code"]
• Explication : "et", "code" sont une sous-chaîne de "leetcode".

Exemple 3 :

• Saisie : mots = ["bleu","vert","bu"]
• Sortie : []
• Explication : Aucune chaîne de mots n'est une sous-chaîne d'une autre chaîne.

Contraintes :

• 1 <= mots.longueur <= 100
• 1 <= mots[i].length <= 30
• les mots [i] ne contiennent que des lettres anglaises minuscules.
• Toutes les chaînes de mots sont uniques.

Indice :

1. Bruteforce pour déterminer si une chaîne est une sous-chaîne d'une autre ou utiliser l'algorithme KMP.

Solution :

Nous devons trouver toutes les chaînes du tableau de mots qui sont des sous-chaînes d'un autre mot du tableau, vous pouvez utiliser une approche par force brute. L'approche consiste à vérifier chaque chaîne de la liste et à vérifier s'il s'agit d'une sous-chaîne d'une autre chaîne.

Implémentons cette solution en PHP : 1408. Correspondance de chaînes dans un tableau

<?php
/**
 * @param String[] $words
 * @return String[]
 */
function stringMatching($words) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$words = ["mass", "as", "hero", "superhero"];
print_r(stringMatching($words));

// Example 2
$words = ["leetcode", "et", "code"];
print_r(stringMatching($words));

// Example 3
$words = ["blue", "green", "bu"];
print_r(stringMatching($words));
?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li>La fonction stringMatching parcourt tous les mots du tableau d'entrée.</li>
<li>Pour chaque mot, il le compare à tous les autres mots du tableau à l'aide d'une boucle imbriquée.</li>
<li>Il utilise la fonction strpos() de PHP pour vérifier si une chaîne est une sous-chaîne d'une autre. La fonction strpos() renvoie false si la sous-chaîne n'est pas trouvée.</li>
<li>Si une sous-chaîne est trouvée, nous ajoutons le mot au tableau de résultats et sortons de la boucle interne, car nous n'avons besoin d'enregistrer le mot qu'une seule fois.</li>
<li>Enfin, la fonction renvoie le tableau résultat contenant toutes les sous-chaînes.</li>
</ol>

<h3>
  
  
  Complexité temporelle :
</h3>

<ul>
<li>La complexité temporelle est <em><strong>O(n<sup>2</sup> x m)</strong></em>, où <em><strong>n</strong></em> est le nombre de mots et <em><strong>m</strong></em> est la longueur maximale d'un mot. En effet, nous effectuons une recherche de sous-chaîne pour chaque mot dans un mot sur deux.</li>
</ul>

<h3>
  
  
  Exemples de sorties :
</h3>

<p>Pour l'entrée ["mass", "as", "hero", "superhero"], la sortie sera :<br>
</p>

<pre class="brush:php;toolbar:false">Array
(
    [0] => as
    [1] => hero
)

Pour l'entrée ["leetcode", "et", "code"], la sortie sera :

Array
(
    [0] => et
    [1] => code
)

Pour l'entrée ["blue", "green", "bu"], la sortie sera :

Array
(
)

Cette solution fonctionne bien pour les contraintes du problème donné.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!