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]
}
}
Author And Source
この問題について(LeetCode日本語修行8日目- [91- デコード方法]), 我々は、より多くの情報をここで見つけました https://qiita.com/Aethey/items/31c2b6d79bf4ff383103著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .