LeetCode日本語修行8日目- [91- デコード方法]


Decode Ways

参考:https://leetcode.com/problems/decode-ways/

問題の内容:

A-Zの文字を含むメッセージは、以下のマッピングを使って数字にエンコードできます。

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

暗号化されたメッセージを解読するためには、すべての数字をグループ化し、上記のマッピングの逆を使って文字にマッピングする必要があります(複数の方法がある場合もあります)。例えば、"11106 "は次のようにマッピングできます。

グループ化(1 1 10 6)した "AAJF"
グルーピング(11 10 6)を使用した "KJF"
ただし、グルーピング(1 11 06)は、"06 "が "F "にマッピングされないため無効である。"6 "は "06 "とは異なるからだ。

例:

例1:
Input: s = "12"
Output: 2

例2:
Input: s = "226"
Output: 3

例3:
Input: s = "0"
Output: 0

ヒント:

1 <= s.length <= 100
s contains only digits and may contain leading zero(s).


DPを使う。
s.charAt(i)の時
その前の文字の暗号化した後の数字は一桁又は二桁
即ち f(i-1) || f(i-2)
それを判断して、処理します。

class Solution {
    fun numDecodings(s: String): Int {
        var m = s.length
        var array = IntArray(m+1)

        array[0] = 1

        for(i in 1 until array.size){
            if(s[i-1] != '0'){
                array[i] += array[i-1]
            }

            if(i>1 && s[i-2] != '0' && (s[i-2]-'0')*10 + (s[i-1]-'0') <= 26){
                 array[i] += array[i-2]
            }
        }
        return array[m]
    }
}