Meditasi LeetCode: Cara Menyahkod

Mari kita mulakan dengan penerangan untuk masalah ini:

Anda telah memintas mesej rahsia yang dikodkan sebagai rentetan nombor. Mesej itu dikodkan melalui pemetaan berikut:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

Walau bagaimanapun, semasa menyahkod mesej, anda menyedari bahawa terdapat banyak cara berbeza anda boleh menyahkod mesej kerana beberapa kod terkandung dalam kod lain ("2" dan "5" lwn "25").

Sebagai contoh, "11106" boleh dinyahkodkan kepada:

• "AAJF" dengan kumpulan (1, 1, 10, 6)
• "KJF" dengan kumpulan (11, 10, 6)
• Penghimpunan (1, 11, 06) tidak sah kerana "06" bukan kod yang sah (hanya "6" sah).

Nota: mungkin terdapat rentetan yang mustahil untuk dinyahkod.

Memandangkan rentetan s yang mengandungi hanya digit, kembalikan bilangan cara kepada nyahkodnya. Jika keseluruhan rentetan tidak boleh dinyahkodkan dengan cara yang sah, kembalikan 0.

Kes ujian dijana supaya jawapannya muat dalam 32-bit integer.

Contohnya:

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Atau:

Input: s = "226"

Output: 3

Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Atau:

Input: s = "06"

Output: 0

Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

Kekangannya ialah:

• 1 <= s.panjang <= 100
• s mengandungi hanya digit dan mungkin mengandungi sifar pendahuluan.

---

Saya rasa ini adalah salah satu masalah yang anda fikir tidak begitu sukar pada pandangan pertama sehingga anda cuba menyelesaikannya.

Pertama, mari kita mulakan dengan cerapan yang paling mudah: aksara boleh dinyahkodkan sama ada dirinya (sebagai satu aksara sahaja) atau bahagian nombor dua digit.
Jika itu pilihan pertama, kita hanya boleh mempunyai digit dari 1 hingga 9, kerana 0 dengan sendirinya tidak dipetakan kepada apa-apa.
Walau bagaimanapun, nombor dua digit boleh dari 10 hingga 26.

Seperti masalah sebelumnya dalam bab ini, kita boleh mulakan dengan mencipta tatasusunan dp untuk menyimpan bilangan cara untuk menyahkod sehingga setiap aksara semasa kita mengulangi melalui rentetan.
Sangat serupa dengan Memanjat Tangga, kita perlu memulakan tatasusunan kita dengan panjang s.length + 1 kerana kita perlu mempertimbangkan hakikat bahawa kita belum menyahkod apa-apa lagi.
Dalam erti kata lain, apabila tiada aksara, hanya ada satu cara untuk "menyahkod": tidak menyahkod sama sekali.

Jadi, kita boleh memulakan semua nilai sebagai 0s, kecuali untuk indeks pertama yang akan menjadi 1.

let dp = Array.from({ length: s.length + 1 }, () => 0);

dp[0] = 1;




<p>Sekali lagi, sama seperti masalah sebelumnya, kita perlu mengekalkan dua nilai terbawah, jadi kita perlu memulakan slot kedua tatasusunan kita yang sepadan dengan bilangan cara untuk menyahkod aksara pertama dalam rentetan.</p>

<p>Kami tahu bahawa kami tidak boleh menyahkodnya jika ia '0', jadi bilangan cara untuk menyahkodnya ialah 0 dalam kes ini.<br>
Ambil perhatian bahawa <em>tidak dapat menyahkod</em> adalah berbeza daripada <em>tidak melakukan sebarang penyahkodan sama sekali</em>: dalam kes pertama, bilangan cara untuk menyahkod ialah 0, tetapi dalam kes kedua (seperti baru sahaja kami lakukan dengan dp[0]), boleh dikatakan bahawa bilangan cara untuk menyahkod ialah 1.</p>

<p>Dalam semua kes lain, hanya ada <strong>satu</strong> cara untuk menyahkodnya kerana ia hanya satu aksara. Jadi, kami akan memulakan dp[1] dengan sewajarnya:<br>
</p>

<pre class="brush:php;toolbar:false">dp[1] = (s[0] === '0') ? 0 : 1;

Kini kita boleh mula mengulangi daripada indeks ketiga. Kami akan melihat kedua-dua digit sebelumnya dan dua digit sebelumnya pada masa yang sama.

Selagi digit sebelumnya bukan nombor 0, kami boleh menambah apa sahaja yang ada dalam slot tatasusunan kami sebelumnya.

Dan, selagi dua digit sebelumnya membentuk nombor antara 10 dan 26, kita boleh menambah penyelesaian yang sepadan itu juga. Secara keseluruhannya, ia boleh kelihatan seperti ini:

for (let i = 2; i <= s.length; i++) {
  const prevDigit = s[i - 1];
  const twoPrevDigits = s.slice(i - 2, i);
  if (+prevDigit !== 0) {
    dp[i] += dp[i - 1];
  }

  if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
    dp[i] += dp[i - 2];
  }
}

Note

We're converting the string characters to numbers with the handy unary plus operator. We know from the problem constraints that the string s only contains digits.

At this point, we have the result in the last index (which corresponds to s.length) so we can just return it:

function numDecodings(s: string): number {
  /* ... */

  return dp[s.length]; 
}

Overall, this is how our solution looks like:

function numDecodings(s: string): number {
  let dp = Array.from({ length: s.length + 1 }, () => 0);

  dp[0] = 1;
  dp[1] = (s[0] === '0') ? 0 : 1;

  for (let i = 2; i <= s.length; i++) {
    const prevDigit = s[i - 1];
    const twoPrevDigits = s.slice(i - 2, i);
    if (+prevDigit !== 0) {
      dp[i] += dp[i - 1];
    }

    if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
      dp[i] += dp[i - 2];
    }
  }

  return dp[s.length];
}

Time and space complexity

Both the time and space complexity for this solution are $O(n)$O(n) as we iterate through all the characters doing a constant operation, and we have to keep an array whose size will grow as our input size increases.

---

Next up is the problem called Coin Change. Until then, happy coding.

Atas ialah kandungan terperinci Meditasi LeetCode: Cara Menyahkod. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!