Präfix- und Suffixpaare zählen I

3042. Präfix- und Suffixpaare zählen I

Schwierigkeit:Einfach

Themen:Array, String, Trie, Rolling Hash, String Matching, Hash-Funktion

Sie erhalten ein 0-indiziertes String-Array mit Wörtern.

Lassen Sie uns eine boolesche-Funktion isPrefixAndSuffix definieren, die zwei Zeichenfolgen akzeptiert, str1 und str2:

• isPrefixAndSuffix(str1, str2) gibt true zurück, wenn str1 sowohl ein Präfix¹ als auch ein Suffix² von str2 ist, andernfalls false.

Zum Beispiel ist isPrefixAndSuffix("aba", "ababa") wahr, weil "aba" ein Präfix von "ababa" und auch ein Suffix ist, aber isPrefixAndSuffix("abc", "abcd") ist falsch.

Gibt eine Ganzzahl zurück, die die Anzahl der Indexpaare (i, j) angibt, sodass i

Beispiel 1:

• Eingabe:words = ["a","aba","ababa","aa"]
• Ausgabe: 4
• Erklärung: In diesem Beispiel sind die gezählten Indexpaare: i = 0 und j = 1, weil isPrefixAndSuffix("a", "aba") wahr ist. i = 0 und j = 2, weil isPrefixAndSuffix("a", "ababa") wahr ist. i = 0 und j = 3, weil isPrefixAndSuffix("a", "aa") wahr ist. i = 1 und j = 2, weil isPrefixAndSuffix("aba", "ababa") wahr ist. Daher lautet die Antwort 4.

Beispiel 2:

• Eingabe: Wörter = ["pa", "papa", "ma", "mama"]
• Ausgabe: 2
• Erklärung: In diesem Beispiel sind die gezählten Indexpaare: i = 0 und j = 1, weil isPrefixAndSuffix("pa", "papa") wahr ist. i = 2 und j = 3, weil isPrefixAndSuffix("ma", "mama") wahr ist. Daher lautet die Antwort 2.

Beispiel 3:

• Eingabe:words = ["abab","ab"]
• Ausgabe: 0
• Erklärung: In diesem Beispiel ist das einzige gültige Indexpaar i = 0 und j = 1 und isPrefixAndSuffix("abab", "ab") ist falsch. Daher ist die Antwort 0.

Einschränkungen:

• 1
• 1
• Wörter[i] bestehen nur aus englischen Kleinbuchstaben.

Hinweis:

1. Iterieren Sie alle Indexpaare (i, j), sodass i
2. Die Antwort ist die Gesamtzahl der Paare, wobei isPrefixAndSuffix(words[i], Words[j]) == true.

Lösung:

Wir müssen alle Indexpaare (i, j) durchlaufen, wobei i

Lassen Sie uns diese Lösung in PHP implementieren: 3042. Präfix- und Suffixpaare zählen 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
?>

Erläuterung:

1. countPrefixAndSuffixPairs($words):

   • Diese Funktion durchläuft alle möglichen Indexpaare (i, j), sodass i
   • Es ruft isPrefixAndSuffix() auf, um zu prüfen, ob Words[i] sowohl ein Präfix als auch ein Suffix von Words[j] ist.
   • Wenn die Bedingung wahr ist, wird die Anzahl erhöht.

2. isPrefixAndSuffix($str1, $str2):

   • Diese Hilfsfunktion prüft, ob str1 sowohl ein Präfix als auch ein Suffix von str2 ist.
   • Es verwendet substr(), um das Präfix und Suffix von str2 zu extrahieren und sie mit str1 zu vergleichen.
   • Wenn beide Bedingungen wahr sind, wird „true“ zurückgegeben, andernfalls wird „false“ zurückgegeben.

Zeitkomplexität:

• Die zeitliche Komplexität beträgt O(n² x m), wobei n die Länge des Wortarrays und m die durchschnittliche Länge des Wortarrays ist Zeichenfolgen im Array. Dies liegt an den verschachtelten Schleifen und den substr()-Operationen.

Beispielausgabe:

Für die angegebenen Eingabearrays:

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

Diese Lösung sollte innerhalb der gegebenen Einschränkungen effizient funktionieren.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

---

1. Präfix Ein Präfix einer Zeichenfolge ist eine Teilzeichenfolge, die am Anfang der Zeichenfolge beginnt und sich bis zu einem beliebigen Punkt darin erstreckt. ↩

2. Suffix Ein Suffix einer Zeichenfolge ist eine Teilzeichenfolge, die an einer beliebigen Stelle in der Zeichenfolge beginnt und sich bis zu ihrem Ende erstreckt. ↩

Das obige ist der detaillierte Inhalt vonPräfix- und Suffixpaare zählen I. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!