Compter les paires de préfixes et de suffixes I

3042. Compter les paires de préfixes et de suffixes I

Difficulté :Facile

Sujets :Array, String, Trie, Rolling Hash, String Matching, Hash Function

Vous recevez un tableau de chaînes de mots indexé à 0.

Définissons une fonction booléenne isPrefixAndSuffix qui prend deux chaînes, str1 et str2 :

• isPrefixAndSuffix(str1, str2) renvoie true si str1 est à la fois un préfixe¹ et un suffixe² de str2, et false sinon.

Par exemple, isPrefixAndSuffix("aba", "ababa") est vrai car "aba" est un préfixe de "ababa" et aussi un suffixe, mais isPrefixAndSuffix("abc", "abcd") est faux.

Renvoie un entier désignant le nombre de paires d'index (i, j) tel que i

Exemple 1 :

• Saisie : mots = ["a","aba","ababa","aa"]
• Sortie : 4
• Explication : Dans cet exemple, les paires d'index comptées sont : i = 0 et j = 1 car isPrefixAndSuffix("a", "aba") est vrai. i = 0 et j = 2 car isPrefixAndSuffix("a", "ababa") est vrai. i = 0 et j = 3 car isPrefixAndSuffix("a", "aa") est vrai. i = 1 et j = 2 car isPrefixAndSuffix("aba", "ababa") est vrai. Par conséquent, la réponse est 4.

Exemple 2 :

• Saisie : mots = ["pa","papa","ma","mama"]
• Sortie : 2
• Explication : Dans cet exemple, les paires d'index comptées sont : i = 0 et j = 1 car isPrefixAndSuffix("pa", "papa") est vrai. i = 2 et j = 3 car isPrefixAndSuffix("ma", "mama") est vrai. Par conséquent, la réponse est 2.

Exemple 3 :

• Saisie : mots = ["abab","ab"]
• Sortie : 0
• Explication : Dans cet exemple, la seule paire d'index valide est i = 0 et j = 1, et isPrefixAndSuffix("abab", "ab") est faux. Par conséquent, la réponse est 0.

Contraintes :

• 1
• 1
• les mots [i] se composent uniquement de lettres anglaises minuscules.

Indice :

1. Parcourir toutes les paires d'index (i, j), de telle sorte que i
2. La réponse est le nombre total de paires où isPrefixAndSuffix(words[i],words[j]) == true.

Solution :

Nous devons parcourir toutes les paires d'index (i, j) où i

Implémentons cette solution en PHP : 3042. Compter les paires de préfixes et de suffixes I

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

/**
 * Function to check if str1 is both a prefix and a suffix of str2
 *
 * @param $str1
 * @param $str2
 * @return bool
 */
function isPrefixAndSuffix($str1, $str2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Test Cases
$words1 = ["a", "aba", "ababa", "aa"];
$words2 = ["pa", "papa", "ma", "mama"];
$words3 = ["abab", "ab"];

echo countPrefixAndSuffixPairs($words1) . "\n";  // Output: 4
echo countPrefixAndSuffixPairs($words2) . "\n";  // Output: 2
echo countPrefixAndSuffixPairs($words3) . "\n";  // Output: 0
?>

Explication:

1. countPrefixAndSuffixPairs ($words):

   • Cette fonction parcourt toutes les paires d'index possibles (i, j) telles que i
   • Il appelle isPrefixAndSuffix() pour vérifier si les mots[i] sont à la fois un préfixe et un suffixe de mots[j].
   • Si la condition est vraie, cela incrémente le décompte.

2. isPrefixAndSuffix($str1, $str2):

   • Cette fonction d'assistance vérifie si str1 est à la fois un préfixe et un suffixe de str2.
   • Il utilise substr() pour extraire le préfixe et le suffixe de str2 et les compare avec str1.
   • Si les deux conditions sont vraies, cela renvoie vrai, sinon, cela renvoie faux.

Complexité temporelle :

• La complexité temporelle est O(n² x m), où n est la longueur du tableau de mots et m est la longueur moyenne du chaînes dans le tableau. Cela est dû aux boucles imbriquées et aux opérations substr().

Exemple de sortie :

Pour les tableaux d'entrée donnés :

• ["a", "aba", "ababa", "aa"] -> Sortie : 4
• ["pa", "papa", "ma", "maman"] -> Sortie : 2
• ["abab", "ab"] -> Sortie : 0

Cette solution devrait fonctionner efficacement dans les limites données.

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

---

1. Préfixe Un préfixe d'une chaîne est une sous-chaîne qui commence au début de la chaîne et s'étend jusqu'à n'importe quel point de celle-ci. ↩

2. Suffixe Un suffixe d'une chaîne est une sous-chaîne qui commence à n'importe quel point de la chaîne et s'étend jusqu'à sa fin. ↩

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!