Interleaving String

Dynamic Programming

O(m × n) time, O(m × n) space

Advanced

Check if string s3 is formed by interleaving s1 and s2. DP problem where dp[i][j] means s3[0...i+j-1] is interleaving of s1[0...i-1] and s2[0...j-1].

Visualization

Interactive visualization for Interleaving String

Interactive visualization with step-by-step execution

Implementation

Language:

1function isInterleave(s1: string, s2: string, s3: string): boolean {
2  if (s1.length + s2.length !== s3.length) return false;
3  
4  const m = s1.length, n = s2.length;
5  const dp: boolean[][] = Array(m + 1).fill(false).map(() => Array(n + 1).fill(false));
6  
7  dp[0][0] = true;
8  
9  for (let i = 1; i <= m; i++) {
10    dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
11  }
12  
13  for (let j = 1; j <= n; j++) {
14    dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];
15  }
16  
17  for (let i = 1; i <= m; i++) {
18    for (let j = 1; j <= n; j++) {
19      dp[i][j] = (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) ||
20                 (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]);
21    }
22  }
23  
24  return dp[m][n];
25}

Complexity

Time

Best

O(m × n)

Average

O(m × n)

Worst

O(m × n)

Space

Required

O(m × n)

Applications

Use Cases

String validation

Pattern matching

Merge verification

Related Algorithms

0/1 Knapsack Problem

A classic optimization problem where you must select items with given weights and values to maximize total value without exceeding the knapsack's capacity. Each item can be taken only once (0 or 1). This is a fundamental problem in combinatorial optimization, resource allocation, and decision-making scenarios.

Dynamic Programming

Longest Common Subsequence (LCS)

Finds the longest subsequence common to two sequences. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously. This is fundamental in diff utilities, DNA sequence analysis, and version control systems like Git.

Dynamic Programming

Edit Distance (Levenshtein Distance)

Edit Distance, also known as Levenshtein Distance, computes the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one string into another. Named after Soviet mathematician Vladimir Levenshtein who introduced it in 1965, this fundamental algorithm has applications in spell checking, DNA sequence analysis, natural language processing, and plagiarism detection.

Dynamic Programming

Longest Increasing Subsequence (LIS)

Longest Increasing Subsequence (LIS) finds the length of the longest subsequence in an array where all elements are in strictly increasing order. Unlike a subarray, a subsequence doesn't need to be contiguous - elements can be selected from anywhere as long as their order is preserved. This classic DP problem has two solutions: O(n²) dynamic programming and O(n log n) binary search with patience sorting. Applications include stock price analysis, scheduling, Box Stacking Problem, and Building Bridges Problem.

Dynamic Programming