Hitung Pasangan Awalan dan Akhiran I

3042. Kira Pasangan Awalan dan Akhiran I

Kesukaran: Mudah

Topik: Tatasusunan, Rentetan, Trie, Rolling Hash, String Matching, Hash Function

Anda diberi 0-indeks perkataan tatasusunan rentetan.

Mari kita takrifkan fungsi boolean ialahPrefixAndSuffix yang mengambil dua rentetan, str1 dan str2:

• isPrefixAndSuffix(str1, str2) mengembalikan benar jika str1 ialah kedua-duanya awalan¹ dan akhiran² str2, dan palsu sebaliknya.

Sebagai contoh, isPrefixAndSuffix("aba", "ababa") adalah benar kerana "aba" ialah awalan "ababa" dan juga akhiran, tetapi isPrefixAndSuffix("abc", "abcd") adalah palsu.

Kembalikan integer yang menandakan nombor pasangan indeks (i, j) supaya i

Contoh 1:

• Input: perkataan = ["a","aba","ababa","aa"]
• Output: 4
• Penjelasan: Dalam contoh ini, pasangan indeks yang dikira ialah: i = 0 dan j = 1 kerana isPrefixAndSuffix("a", "aba") adalah benar. i = 0 dan j = 2 kerana isPrefixAndSuffix("a", "ababa") adalah benar. i = 0 dan j = 3 kerana isPrefixAndSuffix("a", "aa") adalah benar. i = 1 dan j = 2 kerana isPrefixAndSuffix("aba", "ababa") adalah benar. Oleh itu, jawapannya ialah 4.

Contoh 2:

• Input: perkataan = ["pa","papa","ma","mama"]
• Output: 2
• Penjelasan: Dalam contoh ini, pasangan indeks yang dikira ialah: i = 0 dan j = 1 kerana isPrefixAndSuffix("pa", "papa") adalah benar. i = 2 dan j = 3 kerana isPrefixAndSuffix("ma", "mama") adalah benar. Oleh itu, jawapannya ialah 2.

Contoh 3:

• Input: perkataan = ["abab","ab"]
• Output: 0
• Penjelasan: Dalam contoh ini, satu-satunya pasangan indeks yang sah ialah i = 0 dan j = 1, dan isPrefixAndSuffix("abab", "ab") adalah palsu. Oleh itu, jawapannya ialah 0.

Kekangan:

• 1
• 1
• perkataan[i] hanya terdiri daripada huruf kecil Inggeris.

Petunjuk:

1. Lelaran melalui semua pasangan indeks (i, j), supaya i
2. Jawapannya ialah jumlah bilangan pasangan di mana adalahPrefixAndSuffix(words[i], words[j]) == true.

Penyelesaian:

Kita perlu mengulangi semua pasangan indeks (i, j) di mana i

Mari laksanakan penyelesaian ini dalam PHP: 3042. Kira Pasangan Awalan dan Akhiran 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
?>

Penjelasan:

1. countPrefixAndSuffixPairs($words):

   • Fungsi ini menggelung melalui semua pasangan indeks yang mungkin (i, j) supaya i
   • Ia memanggil isPrefixAndSuffix() untuk menyemak sama ada perkataan[i] ialah kedua-dua awalan dan akhiran perkataan[j].
   • Jika syarat itu benar, ia akan menambah kiraan.

2. isPrefixAndSuffix($str1, $str2):

   • Fungsi pembantu ini menyemak sama ada str1 ialah awalan dan akhiran str2.
   • Ia menggunakan substr() untuk mengekstrak awalan dan akhiran str2 dan membandingkannya dengan str1.
   • Jika kedua-dua syarat adalah benar, ia akan kembali benar, jika tidak, ia akan kembali palsu.

Kerumitan Masa:

• Kerumitan masa ialah O(n² x m), dengan n ialah panjang tatasusunan perkataan dan m ialah purata panjang bagi rentetan dalam tatasusunan. Ini disebabkan oleh gelung bersarang dan operasi substr().

Contoh Output:

Untuk tatasusunan input yang diberikan:

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

Penyelesaian ini harus berfungsi dengan cekap dalam kekangan yang diberikan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

---

1. Awalan Awalan rentetan ialah subrentetan yang bermula dari permulaan rentetan dan memanjang ke mana-mana titik di dalamnya. ↩

2. Akhiran Akhiran rentetan ialah subrentetan yang bermula pada mana-mana titik dalam rentetan dan memanjang ke hujungnya. ↩

Atas ialah kandungan terperinci Hitung Pasangan Awalan dan Akhiran I. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!