πŸŽ’
Technical Interview Study Guide
  • πŸ•Welcome!
  • πŸ₯Getting Started
    • Study Plan
    • Optimizing Revision
    • Summer 2024 Timeline
    • FAQs
  • πŸ₯¨Algorithms
    • Binary Search
    • Sorting
    • Recursion
    • Graph
    • Quick Select
    • Intervals
    • Binary
    • Geometry
    • Dynamic Programming
  • πŸ₯žData Structures
    • Arrays
      • Matrices
    • Strings
    • Linked Lists
      • Doubly Linked Lists
    • Hash Tables
    • Graphs
      • Trees
        • Binary Search Trees
        • Heaps
        • Tries
        • Segment Trees
    • Stacks
    • Queues
      • Double Ended Queues
    • Union-Find Disjoint Set (UFDS)
  • 🍑Problems Guide
    • Dynamic Programming Roadmap
      • Warmup
        • Climbing Stairs
        • Nth Tribonacci Number
        • Perfect Squares
      • Linear Sequence
        • Min Cost to Climb Stairs
        • Minimum Time to Make Rope Colorful
        • House Robber
        • Decode Ways
        • Minimum Cost for Tickets
        • Solving Questions with Brainpower
  • 🍣Other Technical Topics
    • General Problem Solving
    • Runtime Predictions
    • System Design
      • SQL
      • Accessing APIs
    • Operating Systems
  • 🍿Non-technical Topics
    • Behavioral Interviews
    • Resumes
Powered by GitBook
On this page
  • Transitions
  • Top-down
  • Bottom-up
  1. Problems Guide
  2. Dynamic Programming Roadmap
  3. Linear Sequence

Decode Ways

Transitions

  1. If s[i] = '0' , then invalid ways (0)

  2. If s[i] = '1', then we can choose to take s[i] as it is, or pair it with the next digit (no matter what, it will form a valid number)

  3. If s[i] = '2', then we can choose to take s[i] as it is, or pair it with the next digit as long as the next digit is from '0' to '6'

  4. Any other digits have to be taken as it is

Top-down

Modelling the transitions as-is gives us:

dp(i)={0,s[i]=01,iβ‰₯∣s∣dp(i+1),s[i]∉[1,2]dp(i+1)+dp(i+2),s[i]=1∨(s[i]=2∧s[i+1]<6)dp(i) = \begin{cases} 0, s[i] = 0\\ 1, i \geq |s|\\ dp(i+1), s[i] \not \in [1,2]\\ dp(i+1) + dp(i+2), s[i] = 1 \lor (s[i] = 2 \land s[i+1] < 6) \end{cases}dp(i)=βŽ©βŽ¨βŽ§β€‹0,s[i]=01,iβ‰₯∣s∣dp(i+1),s[i]ξ€ βˆˆ[1,2]dp(i+1)+dp(i+2),s[i]=1∨(s[i]=2∧s[i+1]<6)​
def decode_ways(s):
    def ways(i):
        if i >= len(s): return 1
        if s[i] == '0': return 0
        ans = ways(i + 1)
        if i + 1 < len(s) and (s[i] == '1' or (s[i] == '2' and s[i + 1] <= '6')):
            ans += ways(i + 2)
        return ans
    return ways(0)

We can then memoize the value of each recursive call by index i.

Bottom-up

To solve this problem using bottom-up, let's re-frame the problem. However, notice that we cannot use the prefix of the array. This is because if we were to use the prefix s[:i+1], we would need to look-ahead to s[i+1], which should not be available yet. So we can re-framing the problem using suffixes instead:

Given [i,n)[i, n)[i,n), can we find out how many ways there are to form s[iβˆ’1]s[i-1]s[iβˆ’1]?

Trick: Implementing recurrence relations If the recurrence relation looks like dp(i)=dp(iβˆ’1)dp(i) = dp(i - 1)dp(i)=dp(iβˆ’1), then it must be processed from left to right using prefixes. If it looks like dp(i)=dp(i+1)dp(i) = dp(i + 1)dp(i)=dp(i+1), then it must be processed from right to left using suffixes.

Looking at the example above, if we have index i, then we can use the values computed from i+1 onwards to figure out how many ways there are to form s[i:].

This gives us the recurrence relation:

dp(i)={1,i=∣s∣0,s[i]=0dp(i+1),s[i]∉[1,2]dp(i+1)+dp(i+2),s[i]=1∨(s[i]=2∧s[i+1]<6)dp(i) = \begin{cases} 1, i = |s|\\ 0, s[i] = 0\\ dp(i+1), s[i] \not\in [1, 2]\\ dp(i+1) + dp(i+2), s[i] = 1 \lor (s[i] = 2 \land s[i+1] < 6) \end{cases}dp(i)=βŽ©βŽ¨βŽ§β€‹1,i=∣s∣0,s[i]=0dp(i+1),s[i]ξ€ βˆˆ[1,2]dp(i+1)+dp(i+2),s[i]=1∨(s[i]=2∧s[i+1]<6)​

Notice that it looks very similar to the original recurrence as we are essentially doing the same operations.

We can also apply the nnn state caching optimization, where n=2n = 2n=2.

def decode_ways(s):
    n = len(s)
    if n == 1: return 1
    s1, s2 = 1, 0 # s1 -> dp(i+1), s2 -> dp(i+2)
    for i in range(n - 1, -1, -1):
        si = 0 if s[i] == '0' else s1 # equivalent to collapsing the first 3 cases
        if i < n - 1 and (s[i] == '1' or (s[i] == '2' and s[i + 1] <= '6')): 
            si += s2
        s1, s2 = si, s1
    return s1

Note that the default values of s1 and s2 are both derived from the two base cases we have, with s1 = 1 because i = |s| and s2 = 0 because i > |s| (out of bounds so no ways to form it).

PreviousHouse RobberNextMinimum Cost for Tickets

Last updated 1 year ago

🍑