Question: https://oj.leetcode.com/problems/decode-ways/
Question Name: Decode Ways
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | class Solution: # @param s, a string # @return an integer def numDecodings(self, s): # Handle with special cases, string is empty or starting with "0". if s == "" or s[0] == "0": return 0 numDecodingEndingHere = [0] * (len(s) + 1) numDecodingEndingHere[0] = 1 index = 0 while index < len(s) - 1: # We cannot decode one single "0" if s[index] == "0": return 0 # We can decode current character and move to the next position. numDecodingEndingHere[index+1] += numDecodingEndingHere[index] # We can also decode current character and the next one at the smae # time, and then move to the second next position. if s[index] == "1" or (s[index] == "2" and s[index+1] in "0123456"): numDecodingEndingHere[index+2] += numDecodingEndingHere[index] if s[index+1] == "0": # In this case, if the next character is "0", we have to # skip it, because one single "0" is unable to be decoded. index += 1 index += 1 if s[-1] != "0": # The last character could be decoded. numDecodingEndingHere[-1] += numDecodingEndingHere[-2] return numDecodingEndingHere[-1] |
OK, the world has changed… It’s quite normal to see DP in medium level interview questions…
Sheng: That’s definitely the case of your company!
Sad, I am going to retire…