Padanan Rentetan dalam Tatasusunan

1408. Padanan Rentetan dalam Tatasusunan

Kesukaran: Mudah

Topik: Tatasusunan, Rentetan, Padanan Rentetan

Memandangkan tatasusunan perkataan rentetan, kembalikan semua rentetan dalam perkataan yang merupakan subrentetan perkataan lain. Anda boleh mengembalikan jawapan dalam sebarang pesanan.

subrentetan ialah jujukan aksara bersebelahan dalam rentetan

Contoh 1:

• Input: perkataan = ["jisim","sebagai","hero","superhero"]
• Output: ["sebagai","hero"]
• Penjelasan: "as" ialah subrentetan bagi "mass" dan "hero" ialah substring bagi "superhero". ["hero","as"] juga merupakan jawapan yang sah.

Contoh 2:

• Input: perkataan = ["leetcode","et","code"]
• Output: ["et","kod"]
• Penjelasan: "et", "code" ialah subrentetan bagi "leetcode".

Contoh 3:

• Input: perkataan = ["biru","hijau","bu"]
• Output: []
• Penjelasan: Tiada rentetan perkataan merupakan subrentetan rentetan lain.

Kekangan:

• 1
• 1
• perkataan[i] hanya mengandungi huruf kecil Inggeris.
• Semua rentetan perkataan adalah unik.

Petunjuk:

1. Bruteforce untuk mencari sama ada satu rentetan adalah subrentetan yang lain atau gunakan algoritma KMP.

Penyelesaian:

Kita perlu mencari semua rentetan dalam tatasusunan perkataan yang merupakan subrentetan perkataan lain dalam tatasusunan, anda boleh menggunakan pendekatan kekerasan. Pendekatan ini melibatkan menyemak setiap rentetan dalam senarai dan mengesahkan sama ada ia merupakan subrentetan daripada mana-mana rentetan lain.

Mari laksanakan penyelesaian ini dalam PHP: 1408. Padanan Rentetan dalam Tatasusunan

<?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));
?>

Penjelasan:

1. Rentetan fungsi padanan gelung melalui semua perkataan dalam tatasusunan input.
2. Untuk setiap perkataan, ia membandingkannya dengan setiap perkataan lain dalam tatasusunan menggunakan gelung bersarang.
3. Ia menggunakan fungsi strpos() PHP untuk menyemak sama ada satu rentetan ialah subrentetan yang lain. Fungsi strpos() mengembalikan false jika subrentetan tidak ditemui.
4. Jika subrentetan ditemui, kami menambah perkataan itu pada tatasusunan hasil dan keluar daripada gelung dalaman, kerana kami hanya perlu merekodkan perkataan itu sekali sahaja.
5. Akhir sekali, fungsi mengembalikan tatasusunan hasil yang mengandungi semua subrentetan.

Kerumitan Masa:

• Kerumitan masa ialah O(n² x m), dengan n ialah bilangan perkataan dan m ialah panjang maksimum perkataan. Ini kerana kami melakukan carian subrentetan untuk setiap perkataan dalam setiap perkataan lain.

Contoh Output:

Untuk input ["mass", "as", "hero", "superhero"], outputnya ialah:

Array
(
    [0] => as
    [1] => hero
)

Untuk input ["leetcode", "et", "code"], outputnya ialah:

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

Untuk input ["biru", "hijau", "bu"], outputnya ialah:

Array
(
)

Penyelesaian ini berfungsi dengan baik untuk kekangan masalah 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

Atas ialah kandungan terperinci Padanan Rentetan dalam Tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!