Team Rocket's Secret Pokémon Code - codepath/compsci_guides GitHub Wiki

Unit 12 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25 mins
  • 🛠️ Topics: Dynamic Programming

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What is the goal of the problem?
    • The goal is to calculate how many ways the given code (a string of digits) can be decoded into letters.
  • What happens if there’s a leading zero in the code?
    • A string with a leading zero is not valid and cannot be decoded.
HAPPY CASE
Input: 
    s = ""12""
Output: 
    2
Explanation:
    The code ""12"" can be decoded as ""AB"" or ""L"".

EDGE CASE
Input: 
    s = ""06""
Output: 
    0
Explanation:
    The code ""06"" is not valid because there is a leading zero that cannot be decoded.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Arrays or Dynamic Programming, and strategies or patterns in those categories.

For String Decoding Problems, we want to consider the following approaches:

  • Dynamic Programming (DP): We can use a DP array to track the number of ways to decode the message up to each index in the string.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use dynamic programming to keep track of the number of ways to decode the message up to each position in the string. For each digit, check whether it can be decoded as a single digit or as part of a two-digit number.

Steps:

  1. Initialization:

    • If the string is empty or starts with '0', return 0 because no valid decoding is possible.
    • Initialize a DP array where dp[i] represents the number of ways to decode the substring s[:i].

  2. Base Case:

    • dp[0] = 1: There is 1 way to decode an empty string.
    • dp[1] = 1: There is 1 way to decode a single character (if it's valid).

  3. Iterate Through the String:

    • For each character in the string starting from index 2:
      • Check if the current character can be decoded as a valid single digit (1-9).
      • Check if the current character and the previous character can be decoded as a valid two-digit number (10-26).

  4. Return the Result:

    • After processing the entire string, dp[n] will contain the number of ways to decode the entire string.

4: I-mplement

Implement the code to solve the algorithm.

def decode_pokemon_code(s):
    if not s or s[0] == '0':
        return 0
    
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # Base case: one way to decode an empty string
    dp[1] = 1  # Base case: one way to decode if the first character is not '0'
    
    for i in range(2, n + 1):
        # Single digit decoding (must be between '1' and '9')
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]
        
        # Two digit decoding (must be between '10' and '26')
        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i - 2]
    
    return dp[n]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

  • Input: s = ""12""
  • Expected Output: 2

Example 2:

  • Input: s = ""226""
  • Expected Output: 3

Example 3:

  • Input: s = ""06""
  • Expected Output: 0

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the length of the input string.

  • Time Complexity: O(n) because we are iterating through the string once.
  • Space Complexity: O(n) to store the DP array.