Mewtwo's Genetic Fusion - codepath/compsci_guides GitHub Wiki

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

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30 mins
  • 🛠️ Topics: Dynamic Programming, String Interleaving

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 check if dna3 can be formed by interleaving the sequences dna1 and dna2.

  • What are the base cases?

    • If dna3's length does not equal dna1's length + dna2's length, return False.

  • What is interleaving?

    • Interleaving means merging two strings while maintaining the relative order of the characters from both strings.
HAPPY CASE
Input: 
    dna1 = ""aabcc""
    dna2 = ""dbbca""
    dna3 = ""aadbbcbcac""
Output: 
    True
Explanation:
    The sequences can be interleaved to form the target string as shown in the problem description.

EDGE CASE
Input: 
    dna1 = """"
    dna2 = """"
    dna3 = """"
Output: 
    True
Explanation:
    Empty strings can always be interleaved to form an empty string.

2: M-atch

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

For interleaving string problems, we want to consider the following approaches:

  • Dynamic Programming (DP): This problem can be solved using a DP table where we track whether the current index in dna3 can be formed by interleaving parts of dna1 and dna2.
  • 2D Grid Traversal: We'll use a 2D DP table, where each entry dp[i][j] represents whether the first i characters of dna1 and the first j characters of dna2 can interleave to form the first i+j characters of dna3.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use dynamic programming to solve this problem. We'll create a DP table dp[i][j] where each entry is True if the first i characters of dna1 and the first j characters of dna2 can interleave to form the first i + j characters of dna3.

Steps:

  1. Base Case:

    • If dna1 + dna2 combined is not equal to dna3 in length, return False.

  2. DP Table Initialization:

    • Create a DP table dp of size (m + 1) x (n + 1) where m is the length of dna1 and n is the length of dna2.
    • Initialize dp[0][0] to True (an empty string can interleave to form an empty string).

  3. DP Table Update:

    • Update the first row and first column to check if prefixes of dna1 and dna2 alone can form the corresponding prefix of dna3.
    • Iterate through the DP table and update each dp[i][j]:
      • dp[i][j] = True if either:
        • dp[i-1][j] == True and dna1[i-1] == dna3[i + j - 1]
        • dp[i][j-1] == True and dna2[j-1] == dna3[i + j - 1]

  4. Return the Result:

    • The answer will be stored in dp[m][n].

4: I-mplement

Implement the code to solve the algorithm.

def genetic_fusion(dna1, dna2, dna3):
    m, n = len(dna1), len(dna2)
    
    # If the lengths don't match, return False
    if len(dna3) != m + n:
        return False
    
    # Initialize DP table
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    
    # Fill the first row and first column
    for i in range(1, m + 1):
        dp[i][0] = dp[i - 1][0] and dna1[i - 1] == dna3[i - 1]
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j - 1] and dna2[j - 1] == dna3[j - 1]
    
    # Fill the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (dp[i - 1][j] and dna1[i - 1] == dna3[i + j - 1]) or (dp[i][j - 1] and dna2[j - 1] == dna3[i + j - 1])
    
    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: dna1 = ""aabcc"", dna2 = ""dbbca"", dna3 = ""aadbbcbcac""
  • Expected Output: True

Example 2:

  • Input: dna1 = ""aabcc"", dna2 = ""dbbca"", dna3 = ""aadbbbaccc""
  • Expected Output: False

Example 3:

  • Input: dna1 = """", dna2 = """", dna3 = """"
  • Expected Output: True

6: E-valuate

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

Assume m is the length of dna1 and n is the length of dna2.

  • Time Complexity: O(m * n) due to filling the DP table.
  • Space Complexity: O(m * n) for storing the DP table.