• 19.6%

https://leetcode.com/problems/decode-ways/

A message containing letters from A-Z is being encoded to numbers using the following mapping:

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

0ms, 73.36%, September 20, 2016

https://discuss.leetcode.com/topic/7025/a-concise-dp-solution

r2表示开始至i-1的decode ways

https://discuss.leetcode.com/topic/15440/my-c-0ms-dp-solution-o-n

My c++ 0ms DP solution O(n)

#### python

62ms, 23.31%, September 20, 2016

https://discuss.leetcode.com/topic/19042/1-liner-o-1-space

w tells the number of ways

v tells the previous number of ways

d is the current digit

p is the previous digit

#### java

5ms, 27.87%, September 20, 2016

https://discuss.leetcode.com/topic/35840/java-clean-dp-solution-with-explanation

I used a dp array of size n + 1 to save subproblem solutions. dp[0] means an empty string will have one way to decode, dp[1] means the way to decode a string of size 1. I then check one digit and two digit combination and save the results along the way. In the end, dp[n] will be the end result.

https://discuss.leetcode.com/topic/2562/dp-solution-java-for-reference

DP Solution (Java) for reference