Medium — Dynamic Programming | String | Two Pointers

The Problem

Given three strings s1, s2, and s3, determine if s3 can be formed by interleaving the characters of s1 and s2 while maintaining the relative order of characters within each string.

Approach

Use dynamic programming with a 2D table where dp[i][j] represents whether the first i characters of s1 and first j characters of s2 can interleave to form the first i+j characters of s3. Fill the table by checking if characters from s1 or s2 match the current position in s3.

Time: O(mn) · Space: O(mn)

Code

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Get the lengths of s1, s2, and s3.
        m, n, p = len(s1), len(s2), len(s3)

        # If the sum of lengths of s1 and s2 is not equal to the length of s3, return False.
        if m + n != p:
            return False

        # Initialize a 2D DP array dp of size (m + 1) x (n + 1) to store intermediate results.
        dp = [[False] * (n + 1) for _ in range(m + 1)]

        # Base case: dp[0][0] is True since two empty strings can form an empty string.
        dp[0][0] = True

        # Fill in the first row of dp.
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

        # Fill in the first column of dp.
        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]

        # Fill in the rest of dp.
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # For dp[i][j] to be True, one of the following conditions must be met:
                # 1. dp[i-1][j] is True and s1[i-1] matches s3[i+j-1].
                # 2. dp[i][j-1] is True and s2[j-1] matches s3[i+j-1].
                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or (
                    dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
                )

        # The result is stored in dp[m][n].
        return dp[m][n]

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment