Leet Code 91. Decode Ways — Graphically Explained Python3 Solution

-

 

Image for post
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 “1”, I can have the choice of decoding “2” and “22”, and then under “2”, I can decode “2” only or “22” and etc. From below grahp, I can see there are some obvious duplicate calculations (like run into ‘0’ and ‘03’ decoding many times).

Image for post

Best Solution (to me)

I can use Dynamic Programming to solve this. The idea comes from following thoughts: assuming there is a string X(for example, ‘12’) and I know the ways to decode it is 2 ([1,2] or [12]). Now let me append one more char(for example, ‘3’). Obviously, for the new string, the decode way is 2 (by decode 3 to ‘C’ and get [1,2,3] or [12,3]) + 1 (by decode 3 with its previous char ‘2’, and then use adopt the decode ways for ‘1’ which is 1) = 3. So in general, if I use dp[i] for the decode ways of the string ending at index i, I will have

dp[i] = dp[i-1] + dp[i-2] (if 0 < s[i-1] + s[i] ≤ 26)

Above is a raw idea and there are some details to figure out as below.

  1. If s[i] is ‘0’, it must combine with its previous char since ‘0’ cannot be decoded; so in this case, there should be a previous char and it should be either ‘1’ or ‘2’. If s[i] is not ‘0’, then dp[i] = dp[i-1].
  2. if dp[i] is 0, then I need to immediately return 0 which means it’s impossible to decode the whole string. Think about the example like ‘123012592329’, when I iterate to calculate dp[3], the ‘0’ (at index = 3) itself cannot be decoded and even it gets combined with previous char (‘3’), it cannot produce an valid decoded char and hence it makes no sense to continue.
  3. To make sure dp[i-1] and dp[i-2] are always valid, I initiliaze dp=[1,1] and use dp[-1] and dp[-2] instead of dp[i-1] and dp[i-2]. The values of 1s assume there are always 1 way to decode (if not running to “return 0”).


Time & Space Complexity

It takes only one iteration of all input (assuming there are N letters) so the time complexity is O(N).

I use an array to store up to N+1 values (for an initialization value and decode ways of s[:0], s[:1], s[:2] and etc.) so the space needed is propotional to N and hence the space complexity is O(N) as well.

Extended Reading

Python3 cheatsheet:

https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549

Comments

Post a Comment

Popular posts from this blog

Leet Code 84. Largest Rectangle in Histogram — Graphically Explained Python3 Solution

-
Image
  Photo by  Pablo Hermoso  on  Unsplash Problem Description Given  n  non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height =  [2,1,5,6,2,3] . The largest rectangle is shown in the shaded area, which has area =  10  unit. Example: Input: [2,1,5,6,2,3] Output: 10 Solution Obvious Solution The obvious (and brute force) way is to use 2 pointers: left and right. Let left points to index 0 ~ N-1 and then right to left and N-1. For each left and right pair, I can calculate the area[left, right] using (right-left+1) * min(heights[left], heights[left+1],heights[left+2],…,heights[right]). Its time complexity is at least be O(N²). Best Solution (to me) [Credit]  This is described by @ TravellingSalesman  in disucssion area ( https://leetcode.com/problems/largest-rectangle-in-histogram...
Read more

Leet Code 1060. Missing Element in Sorted Array — Explained Python3 Solution

-
Image
Problem Description Given a sorted array  A  of  unique  numbers, find the  K -th  missing number starting from the leftmost number of the array.   Example 1: Input: A = [4,7,9,10] , K = 1 Output: 5 Explanation: The first missing number is 5. Example 2: Input: A = [4,7,9,10] , K = 3 Output: 8 Explanation: The missing numbers are [5,6,8,...], hence the third missing number is 8. Solution Seeing the word " sorted " reminds me that there must be some trick to play with. One common thought of mine is binary lookup , which is used for quickly, in O(logN), to locate a specific element. And it turns out similar thoughts applies to this problem as well. Before getting to that, let me explain the brute force way a little bit. First I need to set a counter to count missing number I find as of now, in the beginning, it will be 0 for sure. Then I can certainly iterate the numbers one by one, the moment I get to index i, I will check if A[i] is the last elemen...
Read more

LeetCode 23. Merge k Sorted Lists— Graphically Explained Python3 Solution

-
Image
  Problem Description You are given an array of  k  linked-lists  lists , each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. Example: Input: lists = [[1,1,5],[1,3,4],[2,6]] Output: [1,1,1,2,3,4,5,6] Explanation: The linked-lists are: [ 1->1->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->1->2->3->4->5->6 Solution Obvious Solution The obvious (and brute force) way is to navigate ALL list items, save them into an array and then sort. The time complexity is: O(kN + kNLog(kN)) since for for total k Lists (each one with average N elements), I need to visit them all and the quick sort on final array takes kNLog(kN). The space complexity is O(kN) as all values will be saved. Best Solution (to me) Since each list is already sorted, I can definitely leverage that. To start with, let me use this example: To show it more clearer, let me put some twists (sh...
Read more