package main

func numDecodings(s string) int {
	// just like the stair jumping problem,
	// solution cnt = last cnt + last last cnt (under some condition)
	strLen := len(s)
	if strLen == 0 || s[0] == '0' {
		return 0
	} else if strLen == 1 {
		return 1
	}
	solutionCnt := make([]int, strLen)
	solutionCnt[0] = 1
	if s[0] == '1' || (s[0] == '2' && s[1] <= '6') {
		solutionCnt[1] = 1
	}
	if s[1] != '0' {
		solutionCnt[1] += solutionCnt[0]
	}
	for i := 2; i < strLen; i++ {
		if s[i-1] == '1' || (s[i-1] == '2' && s[i] <= '6') {
			solutionCnt[i] += solutionCnt[i-2]
		}
		if s[i] != '0' {
			solutionCnt[i] += solutionCnt[i-1]
		}
	}
	return solutionCnt[strLen-1]
}

// func main() {
// 	str := "12345120"
// 	fmt.Println(numDecodings(str))
// }