Kira Bilangan Rentetan Konsisten

1684. Kira Bilangan Rentetan Konsisten

Kesukaran: Mudah

Topik: Tatasusunan, Jadual Hash, Rentetan, Manipulasi Bit, Mengira

Anda diberi rentetan yang dibenarkan yang terdiri daripada aksara yang berbeza dan susunan perkataan rentetan. Rentetan adalah konsisten jika semua aksara dalam rentetan muncul dalam rentetan yang dibenarkan.

Kembalikan bilangan konsisten rentetan dalam perkataan tatasusunan.

Contoh 1:

• Input: dibenarkan = "ab", perkataan = ["ad","bd","aaab","baa","badab"]
• Output: 2
• Penjelasan: Rentetan "aaab" dan "baa" adalah konsisten kerana ia hanya mengandungi aksara 'a' dan 'b'.

Contoh 2:

• Input: dibenarkan = "abc", perkataan = ["a","b","c","ab","ac","bc","abc"]
• Output: 7
• Penjelasan: Semua rentetan adalah konsisten.

Contoh 3:

• Input: dibenarkan = "cad", perkataan = ["cc","acd","b","ba","bac","bad","ac","d"]
• Output: 4
• Penjelasan: Rentetan "cc", "acd", "ac" dan "d" adalah konsisten.

Kekangan:

• 1 <= perkataan.panjang <= 10⁴
• 1 <= dibenarkan.panjang <= 26
• 1 <= perkataan[i].panjang <= 10
• Watak yang dibenarkan adalah berbeza.
• perkataan[i] dan dibenarkan mengandungi hanya huruf kecil Inggeris.

Petunjuk:

1. Rentetan tidak betul jika ia mengandungi aksara yang tidak dibenarkan
2. Kekangan cukup kecil untuk kekerasan

Penyelesaian:

Ideanya adalah untuk menyemak sama ada setiap perkataan dalam tatasusunan perkataan adalah konsisten dengan aksara dalam rentetan yang dibenarkan. Sesuatu perkataan adalah konsisten jika semua aksaranya terdapat dalam rentetan yang dibenarkan.

Rancang

1. Set Aksara Yang Dibenarkan:

   • Kami boleh menukar rentetan yang dibenarkan kepada satu set aksara untuk memeriksa dengan cekap sama ada setiap aksara dalam perkataan wujud dalam set.

2. Semakan Ketekalan Perkataan:

   • Untuk setiap perkataan dalam tatasusunan perkataan, semak sama ada semua aksaranya wujud dalam set yang dibenarkan.

3. Kira Perkataan Konsisten:

   • Mulakan kaunter. Untuk setiap perkataan yang konsisten, tambahkan pembilang.

4. Kembalikan Kiraan:

   • Setelah semua perkataan diproses, kembalikan kiraan perkataan yang konsisten.

Mari laksanakan penyelesaian ini dalam PHP: 1684. Kira Bilangan Rentetan Konsisten

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

// Example usage:

// Example 1:
$allowed = "ab";
$words = ["ad", "bd", "aaab", "baa", "badab"];
echo countConsistentStrings($allowed, $words); // Output: 2

// Example 2:
$allowed = "abc";
$words = ["a","b","c","ab","ac","bc","abc"];
echo countConsistentStrings($allowed, $words); // Output: 7

// Example 3:
$allowed = "cad";
$words =  ["cc","acd","b","ba","bac","bad","ac","d"];
echo countConsistentStrings($allowed, $words); // Output: 4
?>




<h3>
  
  
  Penjelasan:
</h3>

<ol>
<li>
<p><strong>Set Dibenarkan</strong>:</p>

<ul>
<li>Kami mencipta tatasusunan bersekutu $allowedSet di mana setiap kekunci ialah aksara daripada rentetan yang dibenarkan. Ini membolehkan carian pantas.</li>
</ul>
</li>
<li>
<p><strong>Ketekalan Perkataan</strong>:</p>

<ul>
<li>Untuk setiap perkataan dalam tatasusunan perkataan, kami mengulangi aksaranya dan menyemak sama ada ia berada dalam $allowedSet. Jika kita menemui mana-mana watak yang tiada dalam set, perkataan itu ditandakan sebagai tidak konsisten dan kita beralih kepada perkataan seterusnya.</li>
</ul>
</li>
<li>
<p><strong>Mengira</strong>:</p>

<ul>
<li>Setiap kali kami menemui perkataan yang konsisten, kami menambah pembilang $consistentCount.</li>
</ul>
</li>
<li>
<p><strong>Kembalikan Keputusan</strong>:</p>

<ul>
<li>Selepas memproses semua perkataan, kaunter menyimpan bilangan rentetan yang konsisten, yang kami kembalikan.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Kerumitan Masa:
</h3>

<ul>
<li>
<strong>Kerumitan Masa</strong>: O(n * m), dengan n ialah bilangan perkataan dan m ialah purata panjang perkataan. Kami sedang mengulangi semua perkataan dan wataknya.</li>
</ul>

<h3>
  
  
  Contoh Panduan:
</h3>

<p>Untuk input:<br>
</p>

<pre class="brush:php;toolbar:false">$allowed = "ab";
$words = ["ad", "bd", "aaab", "baa", "badab"];

• Kami mencipta satu set: allowedSet = ['a' => benar, 'b' => benar].
• Menyemak setiap perkataan:
  • "iklan" tidak konsisten (mengandungi 'd').
  • "bd" tidak konsisten (mengandungi 'd').
  • "aaab" adalah konsisten (hanya mengandungi 'a' dan 'b').
  • "baa" adalah konsisten (hanya mengandungi 'a' dan 'b').
  • "badab" tidak konsisten (mengandungi 'd').

Oleh itu, fungsi mengembalikan 2.

Pengendalian Kekangan:

• Memandangkan dibenarkan hanya boleh mempunyai sehingga 26 aksara berbeza dan perkataan mempunyai paling banyak 10,000 entri, penyelesaian kekerasan ini cukup cekap memandangkan kekangan. Setiap perkataan boleh mempunyai panjang maksimum 10, menjadikannya boleh diulang ke atas semua aksara.

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 Kira Bilangan Rentetan Konsisten. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!