A message containing letters from
A-Z is being encoded to numbers using the following mapping:'A' -> 1 'B' -> 2 ... 'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message
Given encoded message
"12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding
"12" is 2.
Hide Tags
Dynamic Programming String
My friend was asked this problem in his last round interview with Facebook, he got the offer finally. I didn't do this problem before I heard from him, I was wondering if I could do this onsite without knowing it beforehand.
Till now, after one month's exercise in algorithm problems, I have got some basic perception about some classic methods. For this problem, after I reading it, things came up in my mind is DFS + BackTracking. This is a right point to start this question, then we can directly move to DP without implementing a recursive solution.
I spent quite a while to figure out the relation between subproblems and problems, it turned out that the reason it was so hard is that I didn't really understand what this problem is asking. I want to first see a very similar problem, and then say how this problem is derived from it.
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Hide Tags
Dynamic Programming
At each step you can climb one or two stairs, how many distinct ways to climb to the top?
Let's see the relation between subproblem and problem
DP[i] = DP[i-1] + DP[i-2]
| |____ (This part only exists if DP[i-2] exist)
|_______________(This part only exists if DP[i-1] exist)
The relation is quite easy to understand. You can get to ith stair from (i-1) th stair or from (i-2)th stair if i >2. So the number of ways you reach ith stair will be sum of number of ways to reach (i-1)th and number of ways to reach (i-2)th stair
But when you do this the first time, this relation may not be so easy to think of. Why? If a method is quite simple, but hard to think of, very likely because it relies very much on the 'direction' of your thoughts. And you focus too much on the detail of the problem but never had a chance to take a high overview to get a direction to move forward.
I think this is the philosophy behind Dynamic Programming, you need to have a general sense of how things/problems are 'growing'/building up, before you move to details/conditions on it.
For this problem, the relation is simple, and conditions are few, without analyzing it in right order, we can still get the solution. But when problems become complicate as 'Decide Ways',
if you jump into details without figuring out a overall direction, you gonna get lost the complex details forever.
Let's move back to 'Decode ways'
The relation is :
DP[i] = DP[i-1] + DP[i-2]
\ \_____________(if str[i-2] exists and 10<= int(str[i-1] + str[i]))<=26 )
\__________________(If str[i-1] exists and str[i] != '0' )
It is exactly same relationship, but with more conditions.
I previous analysis, I mentioned many times that first find the 'direction' before analyzing the detail, the direction is the relation, you can see, though details become more complicate but direction is as simple as before. And pause for a second, think about how many possible 'directions' for 1 dimension DP and for 2 dimension DP could there be ?
Though DP is the best way to solve such problems, recursion always is the most thrilling way.
Let's first try to do it in recursion.
class Solution:
# @param {string} s
# @return {integer}
num = 0
def numDecodings(self, s):
self.helper(s)
return Solution.num
def helper(self,s):
if len(s) == 0:
Solution.num+=1
return
for i in xrange(2):
if i+1 <= len(s) and self.isValid(s[:i+1]):
self.helper(s[i+1:])
def isValid(self,s):
if int(s) == 0:
return False
if 0 < int(s) <= 26:
return True
In recursion, how to return and what to return is always the most interesting part. In this summer I will write a subject on recursion, this one must be one of many I want mention.
Then Let's look at DP, which is more efficient and more understandable.
class Solution:
# @param {string} s
# @return {integer}
def numDecodings(self, s):
if not s:
return 0
dp = [0]*(len(s)+1)
dp[0] = 1
for i in xrange(len(s)):
if self.isValid(s[i]):
dp[i+1] = dp[i-1+1]
if i>0 and self.isValid(s[i-1:i+1]):
dp[i+1] += dp[i-2+1]
return dp[-1]
def isValid(self,s):
if int(s) == 0:
return False
if len(s) == 1 and 0<int(s) <10:
return True
if len(s) == 2 and 10 <= int(s) <= 26:
return True
# @param {string} s
# @return {integer}
def numDecodings(self, s):
if not s:
return 0
dp = [0]*(len(s)+1)
dp[0] = 1
for i in xrange(len(s)):
if self.isValid(s[i]):
dp[i+1] = dp[i-1+1]
if i>0 and self.isValid(s[i-1:i+1]):
dp[i+1] += dp[i-2+1]
return dp[-1]
def isValid(self,s):
if int(s) == 0:
return False
if len(s) == 1 and 0<int(s) <10:
return True
if len(s) == 2 and 10 <= int(s) <= 26:
return True
There is really not much to say about DP solution, it is worthy noticing that one entry is prefixed to DP array. This kind of manipulation is needed to prevent indexing out of range while keep thing consistent. Because of this, DP[i] actually corresponds to S[i-1]
