【LeetCode】91. Decode Ways

Summary

Given a non-empty string s containing digits from 0 to 26 with size n, determine the total number of ways to decode it by characters ‘A’ to ‘Z’.

Dynamic Programming

This is a typical dynamic programming problem on a sequence. It is not quite hard to come out the representation of states but, in this problem, several situations need to be considered.

At the beginning, I used F[i] to represent the answer of the subsequence from 0 to i, both inclusively. However, it was quite hard to determine the relationships between F[i] and F[i - 1]. Therefore, I came out another representation.

Let F[i] be the answer of the subsequence from 0 to i, both inclusively, whose all decode ways are end by the character at position i.
Let G[i] be the answer of the subsequence from 0 to i, both inclusively, whose all decode ways are end by the character combined by position i and i - 1.
The final answer will be F[n - 1] + G[n - 1].

After that, we need to consider following rules,

F[0] = 1, G[0] = 0.
s[i] can be along(s[i] != '0'), so F[i] = F[i - 1] + G[i - 1].
s[i] cannot be along, so F[i] = 0.
s[i] can combine with s[i - 1], so G[i] = F[i - 1].
s[i] cannot combine with s[i - 1], so G[i] = 0.
There is a 0 in the string, and no other digits can combine with it.
s[0] == '0', and the answer is 0.

Therefore, for any 1 <= i < n, we may consider two boolean value, can_along and can_combine. If both of them are false, Rule 6 satisfies and just return 0.

Appendix

My Solution