eetcode - decode ways II(kotlin)
level - hard
[質問]
エンコードされた文字列を復号する方法はいくつありますか?
'A'-'Z' -> '1'-'26'
'*' -> '1'-'9'
[example 1]
問題を読むと感じますが、これはdp解を使わないとタイムアウトするからです...
ああ...dpが遅い.
最后に他の人の解答を见てやっと知っています.
良心ではdecode ways 2ではなくdecode ways 1
眠くて字を書く...
うまく説明する自信がない.
dpのサイズは、所定の文字列のサイズで割り当てられる.
このdpの最初の値は、文字列の最初の文字によって決定される.
0一人では来られない、0
*9個あるかもしれません
残り.
上記のように1つ目を設定します
この文字列が上記のように表示されるようになった場合、個別に個数を求めることができます.
前のdp値に乗じて、加算すればいいです.
思ったほど難しくないです.
いつも最初から始めるのは難しい.
もう一つの秘訣がある.
いつもmodulo 10^9+7と言うと
入力した値の範囲はintより大きい...
longタイプに設定しましょう.
常にintに設定
どうしたんですか.と言って変なところをうろうろ…
[質問]
エンコードされた文字列を復号する方法はいくつありますか?
'A'-'Z' -> '1'-'26'
'*' -> '1'-'9'
[example 1]
Input: s = "*"
Output: 9
Explanation: The encoded message can represent any of the encoded messages "1", "2", "3", "4", "5", "6", "7", "8", or "9".
Each of these can be decoded to the strings "A", "B", "C", "D", "E", "F", "G", "H", and "I" respectively.
Hence, there are a total of 9 ways to decode "*".
[example 2]Input: s = "1*"
Output: 18
Explanation: The encoded message can represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19".
Each of these encoded messages have 2 ways to be decoded (e.g. "11" can be decoded to "AA" or "K").
Hence, there are a total of 9 * 2 = 18 ways to decode "1*".
[example 3]Input: s = "2*"
Output: 15
Explanation: The encoded message can represent any of the encoded messages "21", "22", "23", "24", "25", "26", "27", "28", or "29".
"21", "22", "23", "24", "25", and "26" have 2 ways of being decoded, but "27", "28", and "29" only have 1 way.
Hence, there are a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 ways to decode "2*".
[解決策]問題を読むと感じますが、これはdp解を使わないとタイムアウトするからです...
ああ...dpが遅い.
最后に他の人の解答を见てやっと知っています.
良心ではdecode ways 2ではなくdecode ways 1
眠くて字を書く...
うまく説明する自信がない.
dpのサイズは、所定の文字列のサイズで割り当てられる.
このdpの最初の値は、文字列の最初の文字によって決定される.
0一人では来られない、0
*9個あるかもしれません
残り.
上記のように1つ目を設定します
この文字列が上記のように表示されるようになった場合、個別に個数を求めることができます.
前のdp値に乗じて、加算すればいいです.
思ったほど難しくないです.
いつも最初から始めるのは難しい.
もう一つの秘訣がある.
いつもmodulo 10^9+7と言うと
入力した値の範囲はintより大きい...
longタイプに設定しましょう.
常にintに設定
どうしたんですか.と言って変なところをうろうろ…
class Solution {
fun numDecodings(s: String): Int {
val dp = LongArray(s.length)
when(s[0]) {
'0' -> dp[0] = 0
'*' -> dp[0] = 9
else -> dp[0] = 1
}
for(i in 1 until s.length) {
if(s[i] == '*') {
dp[i] = (dp[i] + dp[i-1]*9) % 1000000007
if(s[i-1] == '*') {
dp[i] = (dp[i] + if(i>=2) dp[i-2] * 15 else 15) % 1000000007
} else {
when(s[i-1]) {
'1' -> dp[i] = (dp[i] + if(i>=2) dp[i-2]*9 else 9) % 1000000007
'2' -> dp[i] = (dp[i] + if(i>=2) dp[i-2]*6 else 6) % 1000000007
}
}
} else {
val one = s[i] - '0'
if (one != 0) {
dp[i] += dp[i - 1]
}
if(s[i-1] == '*') {
if(one in 7..9) {
dp[i] = (dp[i] + if(i>=2) dp[i-2] else 1) % 1000000007
} else {
dp[i] = (dp[i] + if(i>=2) dp[i-2]*2 else 2) % 1000000007
}
} else {
val ten = (s[i - 1] - '0') * 10 + one
if (ten in 10..26) {
dp[i] = (dp[i] + if (i >= 2) dp[i - 2] else 1) % 1000000007
}
}
}
}
return dp[s.length-1].toInt()
}
}
Reference
この問題について(eetcode - decode ways II(kotlin)), 我々は、より多くの情報をここで見つけました https://velog.io/@mdok1112/leetcode-decode-ways-IIkotlinテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol