97. Interleaving string

97_solution1_memo.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static const char *a, *b, *c;
static int n, m;
static int *dp; // dp[i * (m + 1) + j], -1 = not computed

static bool f(int i, int j) {
  if (i == n && j == m)
    return true; // used everything
  int *memo = &dp[i * (m + 1) + j];
  if (*memo != -1)
    return *memo;

  int k = i + j; // position in s3
  bool res = false;
  if (i < n && a[i] == c[k])
    res = f(i + 1, j); // take from s1
  if (!res && j < m && b[j] == c[k])
    res = f(i, j + 1); // take from s2

  *memo = res;
  return res;
}

bool isInterleave(char *s1, char *s2, char *s3) {
  n = strlen(s1), m = strlen(s2);
  if (n + m != (int)strlen(s3))
    return false;

  a = s1, b = s2, c = s3;
  dp = malloc((n + 1) * (m + 1) * sizeof(int));
  for (int k = 0; k < (n + 1) * (m + 1); k++)
    dp[k] = -1;
  bool res = f(0, 0);
  free(dp);
  return res;
}

97_solution2_tab.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool isInterleave(char *s1, char *s2, char *s3) {
  int n = strlen(s1), m = strlen(s2);
  if (n + m != (int)strlen(s3))
    return false;

  int w = m + 1;
  bool *dp = calloc((n + 1) * w, sizeof(bool)); // dp[i * w + j]
  dp[0] = true;                                 // empty + empty = empty

  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      if (i == 0 && j == 0)
        continue;
      int k = i + j - 1; // last char of s3 prefix
      bool fromS1 = i > 0 && dp[(i - 1) * w + j] && s1[i - 1] == s3[k];
      bool fromS2 = j > 0 && dp[i * w + (j - 1)] && s2[j - 1] == s3[k];
      dp[i * w + j] = fromS1 || fromS2;
    }
  }
  bool res = dp[n * w + m];
  free(dp);
  return res;
}

97_solution1_memo.cpp

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  bool f(int i, int j, string &s1, string &s2, string &s3,
         vector<vector<int>> &dp) {
    if (i == s1.size() && j == s2.size())
      return true; // used everything
    if (dp[i][j] != -1)
      return dp[i][j];

    int k = i + j; // position in s3
    bool res = false;
    if (i < s1.size() && s1[i] == s3[k])
      res = f(i + 1, j, s1, s2, s3, dp); // take from s1
    if (!res && j < s2.size() && s2[j] == s3[k])
      res = f(i, j + 1, s1, s2, s3, dp); // take from s2

    return dp[i][j] = res;
  }

  bool isInterleave(string s1, string s2, string s3) {
    int n = s1.size(), m = s2.size();
    if (n + m != s3.size())
      return false;

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
    return f(0, 0, s1, s2, s3, dp);
  }
};

97_solution2_tab.cpp

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  bool isInterleave(string s1, string s2, string s3) {
    int n = s1.size(), m = s2.size();
    if (n + m != s3.size())
      return false;

    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
    dp[0][0] = true; // empty + empty = empty

    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= m; j++) {
        if (i == 0 && j == 0)
          continue;
        int k = i + j - 1; // last char of s3 prefix
        bool fromS1 = i > 0 && dp[i - 1][j] && s1[i - 1] == s3[k];
        bool fromS2 = j > 0 && dp[i][j - 1] && s2[j - 1] == s3[k];
        dp[i][j] = fromS1 || fromS2;
      }
    }
    return dp[n][m];
  }
};

97_solution1_memo.go

package dp

func isInterleave(s1 string, s2 string, s3 string) bool {
    n, m := len(s1), len(s2)
    if n+m != len(s3) {
        return false
    }

    dp := make([][]int, n+1) // -1 = not computed, 0 = false, 1 = true
    for i := range dp {
        dp[i] = make([]int, m+1)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }

    var f func(i, j int) bool
    f = func(i, j int) bool {
        if i == n && j == m {
            return true // used everything
        }
        if dp[i][j] != -1 {
            return dp[i][j] == 1
        }

        k := i + j // position in s3
        res := false
        if i < n && s1[i] == s3[k] {
            res = f(i+1, j) // take from s1
        }
        if !res && j < m && s2[j] == s3[k] {
            res = f(i, j+1) // take from s2
        }

        dp[i][j] = 0
        if res {
            dp[i][j] = 1
        }
        return res
    }

    return f(0, 0)
}

97_solution2_tab.go

package dp

func isInterleave(s1 string, s2 string, s3 string) bool {
    n, m := len(s1), len(s2)
    if n+m != len(s3) {
        return false
    }

    dp := make([][]bool, n+1)
    for i := range dp {
        dp[i] = make([]bool, m+1)
    }
    dp[0][0] = true // empty + empty = empty

    for i := 0; i <= n; i++ {
        for j := 0; j <= m; j++ {
            if i == 0 && j == 0 {
                continue
            }
            k := i + j - 1 // last char of s3 prefix
            fromS1 := i > 0 && dp[i-1][j] && s1[i-1] == s3[k]
            fromS2 := j > 0 && dp[i][j-1] && s2[j-1] == s3[k]
            dp[i][j] = fromS1 || fromS2
        }
    }
    return dp[n][m]
}

97_solution1_memo.java

class Solution {
    private Boolean[][] dp; // null = not computed

    private boolean f(int i, int j, String s1, String s2, String s3) {
        if (i == s1.length() && j == s2.length())
            return true; // used everything
        if (dp[i][j] != null)
            return dp[i][j];

        int k = i + j; // position in s3
        boolean res = false;
        if (i < s1.length() && s1.charAt(i) == s3.charAt(k))
            res = f(i + 1, j, s1, s2, s3); // take from s1
        if (!res && j < s2.length() && s2.charAt(j) == s3.charAt(k))
            res = f(i, j + 1, s1, s2, s3); // take from s2

        return dp[i][j] = res;
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length();
        if (n + m != s3.length())
            return false;

        dp = new Boolean[n + 1][m + 1];
        return f(0, 0, s1, s2, s3);
    }
}

97_solution2_tab.java

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length();
        if (n + m != s3.length())
            return false;

        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true; // empty + empty = empty

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i == 0 && j == 0)
                    continue;
                int k = i + j - 1; // last char of s3 prefix
                boolean fromS1 = i > 0 && dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(k);
                boolean fromS2 = j > 0 && dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(k);
                dp[i][j] = fromS1 || fromS2;
            }
        }
        return dp[n][m];
    }
}

97_solution1_memo.js

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function (s1, s2, s3) {
  const n = s1.length, m = s2.length;
  if (n + m !== s3.length) return false;

  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(-1));

  const f = (i, j) => {
    if (i === n && j === m) return true; // used everything
    if (dp[i][j] !== -1) return dp[i][j];

    const k = i + j; // position in s3
    let res = false;
    if (i < n && s1[i] === s3[k]) res = f(i + 1, j); // take from s1
    if (!res && j < m && s2[j] === s3[k]) res = f(i, j + 1); // take from s2

    return (dp[i][j] = res);
  };

  return f(0, 0);
};

97_solution2_tab.js

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function (s1, s2, s3) {
  const n = s1.length, m = s2.length;
  if (n + m !== s3.length) return false;

  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(false));
  dp[0][0] = true; // empty + empty = empty

  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= m; j++) {
      if (i === 0 && j === 0) continue;
      const k = i + j - 1; // last char of s3 prefix
      const fromS1 = i > 0 && dp[i - 1][j] && s1[i - 1] === s3[k];
      const fromS2 = j > 0 && dp[i][j - 1] && s2[j - 1] === s3[k];
      dp[i][j] = fromS1 || fromS2;
    }
  }
  return dp[n][m];
};

97_solution1_memo.py

import sys
from typing import List, Optional


class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m = len(s1), len(s2)
        if n + m != len(s3):
            return False

        sys.setrecursionlimit(max(1000, 2 * (n + m) + 100))  # depth can reach n + m
        dp: List[List[Optional[bool]]] = [[None] * (m + 1) for _ in range(n + 1)]

        def f(i: int, j: int) -> bool:
            if i == n and j == m:
                return True  # used everything
            if dp[i][j] is not None:
                return dp[i][j]

            k = i + j  # position in s3
            res = False
            if i < n and s1[i] == s3[k]:
                res = f(i + 1, j)  # take from s1
            if not res and j < m and s2[j] == s3[k]:
                res = f(i, j + 1)  # take from s2

            dp[i][j] = res
            return res

        return f(0, 0)

97_solution2_tab.py

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m = len(s1), len(s2)
        if n + m != len(s3):
            return False

        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = True  # empty + empty = empty

        for i in range(n + 1):
            for j in range(m + 1):
                if i == 0 and j == 0:
                    continue
                k = i + j - 1  # last char of s3 prefix
                from_s1 = i > 0 and dp[i - 1][j] and s1[i - 1] == s3[k]
                from_s2 = j > 0 and dp[i][j - 1] and s2[j - 1] == s3[k]
                dp[i][j] = from_s1 or from_s2
        return dp[n][m]

97_solution1_memo.rs

impl Solution {
    pub fn is_interleave(s1: String, s2: String, s3: String) -> bool {
        let (a, b, c) = (s1.as_bytes(), s2.as_bytes(), s3.as_bytes());
        if a.len() + b.len() != c.len() {
            return false;
        }

        let mut dp = vec![vec![None; b.len() + 1]; a.len() + 1]; // None = not computed
        Self::f(0, 0, a, b, c, &mut dp)
    }

    fn f(i: usize, j: usize, a: &[u8], b: &[u8], c: &[u8], dp: &mut Vec<Vec<Option<bool>>>) -> bool {
        if i == a.len() && j == b.len() {
            return true; // used everything
        }
        if let Some(res) = dp[i][j] {
            return res;
        }

        let k = i + j; // position in s3
        let mut res = false;
        if i < a.len() && a[i] == c[k] {
            res = Self::f(i + 1, j, a, b, c, dp); // take from s1
        }
        if !res && j < b.len() && b[j] == c[k] {
            res = Self::f(i, j + 1, a, b, c, dp); // take from s2
        }

        dp[i][j] = Some(res);
        res
    }
}

97_solution2_tab.rs

impl Solution {
    pub fn is_interleave(s1: String, s2: String, s3: String) -> bool {
        let (a, b, c) = (s1.as_bytes(), s2.as_bytes(), s3.as_bytes());
        let (n, m) = (a.len(), b.len());
        if n + m != c.len() {
            return false;
        }

        let mut dp = vec![vec![false; m + 1]; n + 1];
        dp[0][0] = true; // empty + empty = empty

        for i in 0..=n {
            for j in 0..=m {
                if i == 0 && j == 0 {
                    continue;
                }
                let k = i + j - 1; // last char of s3 prefix
                let from_s1 = i > 0 && dp[i - 1][j] && a[i - 1] == c[k];
                let from_s2 = j > 0 && dp[i][j - 1] && b[j - 1] == c[k];
                dp[i][j] = from_s1 || from_s2;
            }
        }
        dp[n][m]
    }
}