Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Interleaving String solution and explanation

MediumDynamic ProgrammingString9 min read45.0% acceptanceUpdated 9 Apr 2026
Asked ateBayAxonThoughtspotAmazonMicrosoftBloomberg
+4 moreAppleZohoGoogleMeta
Practise Interleaving String
18:19
Interleaving Strings - Dynamic Programming - Leetcode 97 - PythonNeetCode · 18:19 · 148K viewsWatch on YouTube
9 more videos on this problem
  1. Interleaving Strings - Dynamic Programming - Leetcode 97 - PythonNeetCode · 18:19 · 148K views
  2. Interleaving String | Dynamic Programming | Leetcode #97Techdose · 30:30 · 52K views
  3. Interleaving String | Khandaani Tareeka | Memoization | GOOGLE | Leetcode-97codestorywithMIK · 29:35 · 16K views
  4. 97. Interleaving String (Leetcode Hard)Programming Live with Larry · 21:17 · 2K views
  5. Interleaving String #leetcode #dynamicprogrammingDeepti Talesra · 23:35 · 1K views
  6. Interleaving String | LeetCode 97 DP ExplainedDestination FAANG · 21:59 · 1K views
  7. Daily Leetcode #1242: Aug 25, 2023 - 97. Interleaving StringProgramming Live with Larry · 9:21 · 819 views
  8. LeetCode 97. Interleaving StringHappy Coding · 13:38 · 801 views
  9. Daily Leetcode #428: Jun 02, 2021 - 97. Interleaving StringProgramming Live with Larry · 18:14 · 470 views
  10. 97. Interleaving String | Daily Leetcode Challenge | August | C++ | JavaMayur Programming Club · 31:07 · 358 views

The problem

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1, s2, and s3 consist of lowercase English letters.

Follow up: Could you solve it using only O(s2.length) additional memory space?

Approach overview

Problem Overview: You receive three strings s1, s2, and s3. The task is to determine whether s3 can be formed by interleaving characters from s1 and s2 while preserving the relative order of characters from each string. Characters from both strings can be mixed, but their internal order cannot change.

Approach 1: Pure Recursion (Exponential Time)

The straightforward idea is to try building s3 from left to right. At position k in s3, check whether the character matches the next character in s1 or s2. If both match, branch into two recursive calls. If only one matches, continue with that branch. This approach explores every possible interleaving combination, which leads to O(2^(m+n)) time complexity and O(m+n) recursion stack space. It works conceptually but quickly becomes impractical for larger inputs due to repeated subproblems.

Approach 2: Recursive with Memoization (O(m*n) time, O(m*n) space)

The recursive solution repeatedly checks the same states: positions i in s1 and j in s2. These positions uniquely determine the index k = i + j in s3. Store results of these states in a memo table so each pair (i, j) is computed once. When recursion revisits the same state, return the cached result instead of recomputing. This converts the exponential search into a polynomial solution with O(m*n) time and O(m*n) memory. The method clearly expresses the branching logic while eliminating duplicate work. It fits naturally with problems involving overlapping subproblems in dynamic programming.

Approach 3: Bottom-Up Dynamic Programming (O(m*n) time, O(m*n) space)

The iterative DP version builds a table dp[i][j] representing whether the first i characters of s1 and the first j characters of s2 can form the first i + j characters of s3. Initialize dp[0][0] = true. For each cell, check whether the current character in s3 matches the next character in either string and whether the previous state was valid. The transition becomes:

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])

This approach systematically fills the grid and avoids recursion overhead. Time complexity is O(m*n) and space complexity is also O(m*n). With a small optimization, the DP table can be compressed to a single row for O(n) space. This method highlights how string problems often reduce to grid-style DP similar to edit distance.

Recommended for interviews: The bottom-up dynamic programming approach is what most interviewers expect. Start by explaining the recursive idea to demonstrate understanding of the interleaving decision at each step. Then convert the repeated states into memoization or tabulation to reach the optimal O(m*n) solution. Showing this progression demonstrates strong problem-solving and mastery of dynamic programming patterns.

Approach 1: Dynamic Programming

This approach uses a dynamic programming table to ascertain whether the third string, s3, is an interleaving of s1 and s2. We use a 2D DP array dp[i][j] which signifies if s3[0:i+j] is an interleaving of s1[0:i] and s2[0:j]. A bottom-up approach is taken to fill this table.

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m, l = len(s1), len(s2), len(s3)
        if n + m != l:
            return False
        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = True
        for i in range(n + 1):
            for j in range(m + 1):
                if i > 0:
                    dp[i][j] = dp[i][j] or (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1])
                if j > 0:
                    dp[i][j] = dp[i][j] or (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
        return dp[n][m]
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length();
        int m = s2.length();
        int l = s3.length();
        if (n + m != l) return false;
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i > 0) {
                    dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
                }
                if (j > 0) {
                    dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
                }
            }
        }
        return dp[n][m];
    }
}
#include <vector>
#include <string>

class Solution {
public:
    bool isInterleave(std::string s1, std::string s2, std::string s3) {
        int n = s1.size();
        int m = s2.size();
        int l = s3.size();
        if (n + m != l) return false;
        std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(m + 1, false));
        dp[0][0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                if (i > 0) {
                    dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]);
                }
                if (j > 0) {
                    dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
                }
            }
        }
        return dp[n][m];
    }
};
var isInterleave = function(s1, s2, s3) {
    const n = s1.length;
    const m = s2.length;
    const l = s3.length;
    if (n + m !== l) return false;
    const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(false));
    dp[0][0] = true;
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= m; j++) {
            if (i > 0) {
                dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]);
            }
            if (j > 0) {
                dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]);
            }
        }
    }
    return dp[n][m];
};
#include <stdbool.h>
#include <string.h>

bool isInterleave(char * s1, char * s2, char * s3) {
    int n = strlen(s1);
    int m = strlen(s2);
    int l = strlen(s3);
    if (n + m != l) return false;
    bool dp[n + 1][m + 1];
    memset(dp, false, sizeof dp);
    dp[0][0] = true;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i > 0) {
                dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]);
            }
            if (j > 0) {
                dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
            }
        }
    }
    return dp[n][m];
}
public class Solution {
    public bool IsInterleave(string s1, string s2, string s3) {
        int n = s1.Length;
        int m = s2.Length;
        int l = s3.Length;
        if (n + m != l) return false;
        bool[,] dp = new bool[n + 1, m + 1];
        dp[0, 0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i > 0) {
                    dp[i, j] = dp[i, j] || (dp[i - 1, j] && s1[i - 1] == s3[i + j - 1]);
                }
                if (j > 0) {
                    dp[i, j] = dp[i, j] || (dp[i, j - 1] && s2[j - 1] == s3[i + j - 1]);
                }
            }
        }
        return dp[n, m];
    }
}

In the Python implementation, the dynamic programming table dp is filled similarly. The table tracks whether s3[0:i+j] can be formed by s1[0:i] and s2[0:j]. We check each character's addition from either string matches s3.

Complexity

Time Complexity: O(n * m).

Space Complexity: O(n * m).

Try this approach in the editor

Approach 2: Recursive with Memoization

This recursive approach tries to construct the interleaved string by attempting to use characters from s1 and s2 to match each character of s3. To optimize, memoization is applied to avoid recalculating results for the same subproblems.

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        from functools import lru_cache
        
        @lru_cache(None)
        def helper(i, j):
            if i == len(s1) and j == len(s2): return len(s1) + len(s2) == len(s3)
            if i < len(s1) and s1[i] == s3[i+j] and helper(i+1, j): return True
            if j < len(s2) and s2[j] == s3[i+j] and helper(i, j+1): return True
            return False
        return helper(0, 0) if len(s1) + len(s2) == len(s3) else False
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if ((s1.length() + s2.length()) != s3.length()) return false;
        return isInterleave(s1, 0, s2, 0, s3, 0, new HashMap<String, Boolean>());
    }
    private boolean isInterleave(String s1, int i, String s2, int j, String s3, int k, Map<String, Boolean> memo) {
        if (k == s3.length()) return true;
        String key = i + ":" + j;
        if (memo.containsKey(key)) return memo.get(key);
        boolean ans = false;
        if (i < s1.length() && s1.charAt(i) == s3.charAt(k)) {
            ans = isInterleave(s1, i + 1, s2, j, s3, k + 1, memo);
        }
        if (!ans && j < s2.length() && s2.charAt(j) == s3.charAt(k)) {
            ans = isInterleave(s1, i, s2, j + 1, s3, k + 1, memo);
        }
        memo.put(key, ans);
        return ans;
    }
}
#include <vector>
#include <string>
#include <unordered_map>

class Solution {
public:
    bool isInterleave(std::string s1, std::string s2, std::string s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        std::unordered_map<int, bool> memo;
        return checkInterleave(s1, 0, s2, 0, s3, 0, memo);
    }
private:
    bool checkInterleave(const std::string &s1, int i, const std::string &s2, int j, const std::string &s3, int k, std::unordered_map<int, bool> &memo) {
        if (k == s3.size()) return true;
        int key = i * s3.size() + j;
        if (memo.find(key) != memo.end()) return memo[key];
        bool ans = false;
        if (i < s1.size() && s1[i] == s3[k]) ans = ans || checkInterleave(s1, i + 1, s2, j, s3, k + 1, memo);
        if (j < s2.size() && s2[j] == s3[k]) ans = ans || checkInterleave(s1, i, s2, j + 1, s3, k + 1, memo);
        return memo[key] = ans;
    }
};
var isInterleave = function(s1, s2, s3) {
    if (s1.length + s2.length !== s3.length) return false;

    let memo = new Map();

    const recurse = (i, j) => {
        if (i + j === s3.length) return true;
        let key = `${i}-${j}`;
        if (memo.has(key)) return memo.get(key);

        if (i < s1.length && s1[i] === s3[i + j] && recurse(i + 1, j)) {
            memo.set(key, true);
            return true;
        }

        if (j < s2.length && s2[j] === s3[i + j] && recurse(i, j + 1)) {
            memo.set(key, true);
            return true;
        }

        memo.set(key, false);
        return false;
    };

    return recurse(0, 0);
};
#include <stdbool.h>
#include <string.h>

#define MAX 101

bool recursiveMemo(char* s1, char* s2, char* s3, int i, int j, int memo[MAX][MAX], int n, int m) {
    if (i == n && j == m) return true;
    if (memo[i][j] != -1) return memo[i][j];
    int k = i + j;
    bool ans = false;
    if (i < n && s1[i] == s3[k]) ans |= recursiveMemo(s1, s2, s3, i + 1, j, memo, n, m);
    if (j < m && s2[j] == s3[k]) ans |= recursiveMemo(s1, s2, s3, i, j + 1, memo, n, m);
    return memo[i][j] = ans;
}

bool isInterleave(char * s1, char * s2, char * s3) {
    int n = strlen(s1);
    int m = strlen(s2);
    int l = strlen(s3);
    if (n + m != l) return false;
    int memo[MAX][MAX];
    memset(memo, -1, sizeof(memo));
    return recursiveMemo(s1, s2, s3, 0, 0, memo, n, m);
}
using System;
using System.Collections.Generic;

public class Solution {
    public bool IsInterleave(string s1, string s2, string s3) {
        if (s1.Length + s2.Length != s3.Length)
            return false;

        return IsInterleave(s1, 0, s2, 0, s3, 0, new Dictionary<string, bool>());
    }

    private bool IsInterleave(string s1, int i, string s2, int j, string s3, int k, Dictionary<string, bool> memo) {
        if (k == s3.Length)
            return true;

        string key = i + ":" + j;
        if (memo.ContainsKey(key))
            return memo[key];

        bool ans = false;
        if (i < s1.Length && s1[i] == s3[k])
            ans = IsInterleave(s1, i + 1, s2, j, s3, k + 1, memo);

        if (!ans && j < s2.Length && s2[j] == s3[k])
            ans = IsInterleave(s1, i, s2, j + 1, s3, k + 1, memo);

        memo[key] = ans;
        return ans;
    }
}

Python's implementation utilizes the @lru_cache decorator to memoize recursive results automatically. It recurses through ranges of characters, checking if continuing would result in an interleave.

Complexity

Time Complexity: O(n * m), due to caching all subproblems.

Space Complexity: O(n * m), due to stack space and memoization.

Try this approach in the editor

Approach 3: Memoization Search

Let's denote the length of string s_1 as m and the length of string s_2 as n. If m + n neq |s_3|, then s_3 is definitely not an interleaving string of s_1 and s_2, so we return false.

Next, we design a function dfs(i, j), which represents whether the remaining part of s_3 can be interleaved from the ith character of s_1 and the jth character of s_2. The answer is dfs(0, 0).

The calculation process of function dfs(i, j) is as follows:

If i geq m and j geq n, it means that both s_1 and s_2 have been traversed, so we return true.

If i < m and s_1[i] = s_3[i + j], it means that the character s_1[i] is part of s_3[i + j]. Therefore, we recursively call dfs(i + 1, j) to check whether the next character of s_1 can match the current character of s_2. If it can match, we return true.

Similarly, if j < n and s_2[j] = s_3[i + j], it means that the character s_2[j] is part of s_3[i + j]. Therefore, we recursively call dfs(i, j + 1) to check whether the next character of s_2 can match the current character of s_1. If it can match, we return true.

Otherwise, we return false.

To avoid repeated calculations, we can use memoization search.

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of strings s_1 and s_2 respectively.

function isInterleave(s1: string, s2: string, s3: string): boolean {
    const m = s1.length;
    const n = s2.length;
    if (m + n !== s3.length) {
        return false;
    }
    const f: number[][] = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    const dfs = (i: number, j: number): boolean => {
        if (i >= m && j >= n) {
            return true;
        }
        if (f[i][j]) {
            return f[i][j] === 1;
        }
        f[i][j] = -1;
        if (i < m && s1[i] === s3[i + j] && dfs(i + 1, j)) {
            f[i][j] = 1;
        }
        if (f[i][j] === -1 && j < n && s2[j] === s3[i + j] && dfs(i, j + 1)) {
            f[i][j] = 1;
        }
        return f[i][j] === 1;
    };
    return dfs(0, 0);
}
func isInterleave(s1 string, s2 string, s3 string) bool {
	m, n := len(s1), len(s2)
	if m+n != len(s3) {
		return false
	}

	f := map[int]bool{}
	var dfs func(int, int) bool
	dfs = func(i, j int) bool {
		if i >= m && j >= n {
			return true
		}
		if v, ok := f[i*200+j]; ok {
			return v
		}
		k := i + j
		f[i*200+j] = (i < m && s1[i] == s3[k] && dfs(i+1, j)) || (j < n && s2[j] == s3[k] && dfs(i, j+1))
		return f[i*200+j]
	}
	return dfs(0, 0)
}
impl Solution {
    #[allow(dead_code)]
    pub fn is_interleave(s1: String, s2: String, s3: String) -> bool {
        let n = s1.len();
        let m = s2.len();

        if s1.len() + s2.len() != s3.len() {
            return false;
        }

        let mut record = vec![vec![-1; m + 1]; n + 1];

        Self::dfs(
            &mut record,
            n,
            m,
            0,
            0,
            &s1.chars().collect(),
            &s2.chars().collect(),
            &s3.chars().collect(),
        )
    }

    #[allow(dead_code)]
    fn dfs(
        record: &mut Vec<Vec<i32>>,
        n: usize,
        m: usize,
        i: usize,
        j: usize,
        s1: &Vec<char>,
        s2: &Vec<char>,
        s3: &Vec<char>,
    ) -> bool {
        if i >= n && j >= m {
            return true;
        }

        if record[i][j] != -1 {
            return record[i][j] == 1;
        }

        // Set the initial value
        record[i][j] = 0;
        let k = i + j;

        // Let's try `s1` first
        if i < n && s1[i] == s3[k] && Self::dfs(record, n, m, i + 1, j, s1, s2, s3) {
            record[i][j] = 1;
        }

        // If the first approach does not succeed, let's then try `s2`
        if record[i][j] == 0
            && j < m
            && s2[j] == s3[k]
            && Self::dfs(record, n, m, i, j + 1, s1, s2, s3)
        {
            record[i][j] = 1;
        }

        record[i][j] == 1
    }
}
Try this approach in the editor

Approach 4: Dynamic Programming

We can convert the memoization search in Solution 1 into dynamic programming.

We define f[i][j] to represent whether the first i characters of string s_1 and the first j characters of string s_2 can interleave to form the first i + j characters of string s_3. When transitioning states, we can consider whether the current character is obtained from the last character of s_1 or the last character of s_2. Therefore, we have the state transition equation:

$ f[i][j] = \begin{cases} f[i - 1][j] & if s_1[i - 1] = s_3[i + j - 1] \ or f[i][j - 1] & if s_2[j - 1] = s_3[i + j - 1] \ false & otherwise \end{cases}

where f[0][0] = true indicates that an empty string is an interleaving string of two empty strings.

The answer is f[m][n].

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of strings s_1 and s_2$ respectively.

function isInterleave(s1: string, s2: string, s3: string): boolean {
    const m = s1.length;
    const n = s2.length;
    if (m + n !== s3.length) {
        return false;
    }
    const f: boolean[][] = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(false));
    f[0][0] = true;
    for (let i = 0; i <= m; ++i) {
        for (let j = 0; j <= n; ++j) {
            const k = i + j - 1;
            if (i > 0 && s1[i - 1] === s3[k]) {
                f[i][j] = f[i - 1][j];
            }
            if (j > 0 && s2[j - 1] === s3[k]) {
                f[i][j] = f[i][j] || f[i][j - 1];
            }
        }
    }
    return f[m][n];
}
func isInterleave(s1 string, s2 string, s3 string) bool {
	m, n := len(s1), len(s2)
	if m+n != len(s3) {
		return false
	}
	f := make([][]bool, m+1)
	for i := range f {
		f[i] = make([]bool, n+1)
	}
	f[0][0] = true
	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			k := i + j - 1
			if i > 0 && s1[i-1] == s3[k] {
				f[i][j] = f[i-1][j]
			}
			if j > 0 && s2[j-1] == s3[k] {
				f[i][j] = (f[i][j] || f[i][j-1])
			}
		}
	}
	return f[m][n]
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Dynamic Programming

Time Complexity: O(n * m).

Space Complexity: O(n * m).

Recursive with Memoization

Time Complexity: O(n * m), due to caching all subproblems.

Space Complexity: O(n * m), due to stack space and memoization.

Memoization Search–
Dynamic Programming–

Complexity analysis

ApproachTimeSpaceWhen to Use
Pure RecursionO(2^(m+n))O(m+n)Useful for understanding the interleaving decision logic before optimization
Recursion with MemoizationO(m*n)O(m*n)When you want a clear top‑down solution that avoids recomputation
Bottom-Up Dynamic ProgrammingO(m*n)O(m*n)Standard interview solution; predictable performance and easy to reason about
Space Optimized DPO(m*n)O(n)When memory is constrained and only the previous row of DP is needed

Frequently asked questions

Is Interleaving String easy or hard?

Interleaving String is generally considered a medium difficulty problem. The challenge comes from identifying the correct DP state and handling branching conditions when characters from both strings match the next character in s3.

Interleaving String Python/Java solution

Both Python and Java implementations typically use dynamic programming. Create a boolean dp array where dp[i][j] indicates whether the first i characters of s1 and j characters of s2 can form s3 up to index i+j. The transition checks characters from both strings and builds the solution iteratively.

How to solve Interleaving String in O(n)?

The time complexity cannot be reduced to O(n) because every combination of indices from s1 and s2 must be considered. However, the space complexity can be optimized to O(n) by storing only one row of the dynamic programming table while iterating through the strings.

What is the best approach for Interleaving String?

Dynamic programming with a 2D table is the most reliable approach. The state dp[i][j] represents whether the first i characters of s1 and j characters of s2 can form the first i+j characters of s3. This solution runs in O(m*n) time and avoids the exponential branching seen in plain recursion.

Is Interleaving String asked at Google/Amazon/Meta?

Interleaving String is a classic dynamic programming interview problem and has appeared in interviews at large tech companies including Amazon, Google, and Meta. Interviewers use it to test understanding of DP state design and overlapping subproblems in string manipulation tasks.

What data structure is used in Interleaving String?

The core data structure is a 2D dynamic programming table that stores boolean values for substring combinations. Some implementations also use recursion with a memoization hash map or matrix to cache previously computed states.

What is the time complexity of Interleaving String?

The optimal solution runs in O(m*n) time where m and n are the lengths of s1 and s2. Each pair of indices (i, j) is processed once in the DP table. Space complexity is O(m*n) for the full table or O(n) with space optimization.

Comments

Now write it yourselfClose this page and solve Interleaving String in the editor, without looking.
Practise Interleaving String