View on LeetCode

Approach: DP where dp[i] is ways to decode s[:i]; add dp[i-1] if s[i-1] is a valid single digit, and dp[i-2] if s[i-2:i] is a valid two-digit code (10–26).

Complexity: O(n) time, O(n) space

go

func numDecodings(s string) int {
	n := len(s)
	if n == 0 || s[0] == '0' {
		return 0
	}
	dp := make([]int, n+1)
	dp[0], dp[1] = 1, 1
	for i := 2; i <= n; i++ {
		if s[i-1] != '0' {
			dp[i] += dp[i-1]
		}
		val := (s[0]-'0')*10 + (s[1] - '0')
		if val >= 10 && val <= 26 {
			dp[i] += dp[i-2]
		}
	}
	return dp[n]
}