Katara’s Waterbending Mastery - 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 the minimum number of operations required to convert form1 into form2.
  • What are the allowed operations?
    • The allowed operations are inserting, deleting, and replacing a move.
  • Is there a base case?
    • Yes, converting an empty string into another string would require inserting all characters.
HAPPY CASE
Input: 
    form1 = ""tide""
    form2 = ""wave""
Output: 
    3
Explanation:
    tide -> wide (replace 't' with 'w')
    wide -> wade (replace 'i' with 'a')
    wade -> wave (replace 'd' with 'v')

EDGE CASE
Input: 
    form1 = """"
    form2 = ""wave""
Output: 
    4
Explanation:
    An empty string requires four insertions to match ""wave"".

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 Waterbending Mastery, we want to consider the following approaches:

  • Dynamic Programming (DP): The problem involves finding the minimum number of operations required to convert one string into another, which is a classic DP problem.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We can use a dynamic programming approach to solve this problem. The idea is to use a DP table where dp[i][j] represents the minimum number of operations required to convert the first i characters of form1 into the first j characters of form2.

Steps:

  1. Initialize a DP Table:

    • Create a (m+1) x (n+1) DP table where m is the length of form1 and n is the length of form2.
    • dp[i][0] represents converting form1[:i] into an empty string, which would require i deletions.
    • dp[0][j] represents converting an empty string into form2[:j], which would require j insertions.

  2. Fill the Table:

    • For each cell (i, j):
      • If form1[i-1] == form2[j-1], no operation is needed, so set dp[i][j] = dp[i-1][j-1].
      • Otherwise, take the minimum of the following three operations and add 1:
        • Insert: dp[i][j-1] + 1
        • Delete: dp[i-1][j] + 1
        • Replace: dp[i-1][j-1] + 1

  3. Return the Result:

    • The value in dp[m][n] contains the minimum number of operations required to convert form1 into form2.

4: I-mplement

Implement the code to solve the algorithm.

def waterbending_mastery(form1, form2):
    m, n = len(form1), len(form2)

    # Create a (m+1) x (n+1) DP table
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Initialize base cases
    for i in range(1, m + 1):
        dp[i][0] = i  # Deleting all characters from form1
    for j in range(1, n + 1):
        dp[0][j] = j  # Inserting all characters into form1

    # Fill the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if form1[i - 1] == form2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # No operation needed
            else:
                dp[i][j] = min(
                    dp[i][j - 1] + 1,  # Insert
                    dp[i - 1][j] + 1,  # Delete
                    dp[i - 1][j - 1] + 1  # Replace
                )

    # The last cell contains the answer
    return dp[m][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: form1 = ""tide"", form2 = ""wave""
  • Expected Output: 3

Example 2:

  • Input: form1 = ""intention"", form2 = ""execution""
  • Expected Output: 5

6: E-valuate

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

Assume m is the length of form1 and n is the length of form2.

  • Time Complexity: O(m * n) because we need to fill a DP table with dimensions (m+1) x (n+1).
  • Space Complexity: O(m * n) to store the DP table.