Decode Ways
MediumThe problem
A message of letters was turned into digits using A=1, B=2, ... Z=26. Given the digit string s, return the number of different ways to read it back as letters. Numbers with a leading zero such as "06" are not valid codes.
- Example 1Input: s = "12"Output: 2
It can be read as "AB" (1, 2) or "L" (12).
- Example 2Input: s = "226"Output: 3
"BZ" (2, 26), "VF" (22, 6) or "BBF" (2, 2, 6).
- Example 3Input: s = "06"Output: 0
"06" is not a valid code and a lone 0 is not a letter.
- 1 ≤ len(s) ≤ 100
- s has only digits
- The answer fits in a 32-bit integer
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
The last one digit or the last two digits form a letter. When is each valid?
The idea
dp[i] = (s[i−1] ≠ "0" ? dp[i−1] : 0) + (10 ≤ two-digit ≤ 26 ? dp[i−2] : 0), with dp[0]=1.
Target: O(n) time, O(1) space
Go function shape
func numDecodings(s string) intReference solution
Tested with go test. Try it yourself first, then compare.
// NumDecodings: "12" can be "AB" (1,2) or "L" (12).
// dp[i] = ways to decode the first i digits = (last digit alone is 1-9) + (last two digits are 10-26).
func NumDecodings(s string) int {
if len(s) == 0 || s[0] == '0' {
return 0
}
prev2, prev1 := 1, 1 // ways for 0 digits and for 1 digit
for i := 2; i <= len(s); i++ {
cur := 0
if s[i-1] != '0' {
cur += prev1
}
if two := int(s[i-2]-'0')*10 + int(s[i-1]-'0'); two >= 10 && two <= 26 {
cur += prev2
}
prev2, prev1 = prev1, cur
}
return prev1
}