Leet Code 91. Decode Ways — Graphically Explained Python3 Solution
Photo by Michael Dziedzic on Unsplash Problem Description A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. The answer is guaranteed to fit in a 32-bit integer. Example 1: Input: s = "12203" Output: 2 Explanation: It could be decoded as "ABTC" (1,2,20,3) or "LTC" (12,20,3). Example 2: Input: s = "20103" Output: 1 Explanation: It could be decoded as "TJC" (20, 10, 3). Example 3: Input: s = "2030" Output: 0 Explanation: 30 could be decoded. Solution Obvious Solution The obvious (and brute force) way is to try every possible way. The solution looks like below tree and I will calculate final valid path number as the result. For example 1, it’s like a DFS way: first I can decode “1” or “12”, and then under “