aboutsummaryrefslogtreecommitdiff
path: root/decode_ways.py
diff options
context:
space:
mode:
Diffstat (limited to 'decode_ways.py')
-rw-r--r--decode_ways.py43
1 files changed, 43 insertions, 0 deletions
diff --git a/decode_ways.py b/decode_ways.py
new file mode 100644
index 0000000..0689aed
--- /dev/null
+++ b/decode_ways.py
@@ -0,0 +1,43 @@
+# 91. Decode Ways
+
+"""
+a message containing letters from a - z can be encoded into numbers using the
+following mapping: a -> 1, b -> 2, ..., z -> 26. to decode an encoded
+message, all the digits must be grouped then mapped back into letters using
+the reverse of the mapping above (there may be multiple ways). for example,
+"11106" can be mapped into: "aajf" with the grouping ' 1 1 10 6', "kjf" with
+the grouping '11 10 6'. note that the grouping '(1 11 06)' because '06'
+cannot be mapped into "f" because '6' is different from '06'. given a string
+'s' containing only digits, return the number of ways to decode it. the test
+cases are generated so that the answer fits in a 32-bit integer
+"""
+
+
+class Solution(object):
+ def numDecodings(self, s):
+ """
+ :type s: str
+ :rtype: int
+ """
+ if s == "0":
+ return 0
+ dp1 = int(s[-1] != "0")
+ dp2 = 1
+ i = len(s) - 2
+ while i >= 0:
+ if s[i] == "0":
+ dp0 = 0
+ else:
+ dp0 = dp1
+ if (s[i] == "1") or (s[i] == "2" and eval(s[i + 1]) < 7):
+ dp0 += dp2
+ i -= 1
+ dp0, dp1, dp2 = 0, dp0, dp1
+ return dp1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numDecodings("12"))
+ print(obj.numDecodings("226"))
+ print(obj.numDecodings("06"))