[LeetCode] 91. Decode Ways

轉自LeetCode

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

<Solution>

根據經驗，string 的相關問題可以先用 dynamic programming 的方式思考 (參考資料)

舉例 : s = "1210"

首先準備一個長度為 s.length() + 1 的 dp array

dp[i] 表示 s[i-1] 可以有幾種解碼方式

dp[0] = 1，這是因為空字串只有一種解碼方式

dp[1] : s[0] = '1'，本身可以單獨解碼，因為是第一個數，也無法和前面的字元組合在一起，所以 dp[1] = dp[0] = 1

dp[2] : s[1] = '2'，本身可以單獨解碼，所以先把 dp[2] = dp[1] = 1。 這時候再看和前面一個字元組合後，是不是小於 26，是的話，代表可以和前面一個字元視作是同一個字母，所以 dp[2] += dp[0]，dp[2] = 2

<補充解釋>
'1' + '2' : 一定有1、2分開看這一種解法 => dp[2] = dp[1]
因為 '1' + '2' 也可以看做 '12'，也就是從空字串直接變成 '12' 這種解法 => dp[2] += dp[0]
所以其實可以看成爬梯子，一次只能爬一步或兩步(類似題目 climbing stairs)
因此當前的位置，可以從前一步來，或是從前兩步來
在這題，必須要多檢查一些條件，來確定前一步或前兩步來是符合規則的

dp[3] : s[2] = '1'，同理，先 dp[3] = dp[2] = 2，然後 dp[3] += dp[1]，dp[3] = 3

dp[4] : s[3] = '0'，因為 0 不能單獨解碼，所以 dp[4] = 0，然後看看和前面一個字元組合後，是不是小於 26，是，所以 dp[4] += dp[2]，dp[4] = 2

最後答案就是 dp[4] = 2

從上面可以推出來 dp 的公式

dp[i] += (s[i-1] == '0') ? 0 : dp[i-1] and

if s[i-2] + s[i-1] <= 26 then dp[i] += dp[i-2]

code 如下
c++

kotlin
還有一種解法，也是 DP 的觀念，但空間複雜度可以變為 O(1) (參考資料)

讓 d1 代表前一步的解法，d2 代表前兩步的解法

初始值 d1 = 0 (空字串)，d2 = 0

一樣是使用上面推導出來的公式來做運算

每次運算後，d1 就會是目前所在位置的總解法

然後記得要把 d2 變成之前的 d1

code 如下