题目

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 they are divided into non-empty substrings 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:

image.png

  1. Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
  2. Output: true

Example 2:

  1. Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
  2. Output: false

Example 3:

  1. Input: s1 = "", s2 = "", s3 = ""
  2. 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?

题意

判断字符串s1和s2能否通过间隔插入的方法得到s3。

思路

动态规划。dp[i][j]为布尔值，表示s1.substring(0,i)和s2.substring(0,j)能否通过间隔插入组成s3.substring(0, i + j)。

Follow up可以用滚动数组优化到O(s2.length)。

代码实现

Java

  1. class Solution {
  2.     public boolean isInterleave(String s1, String s2, String s3) {
  3.         if (s3.length() != s1.length() + s2.length()) return false;      
  5.         boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
  7.         for (int i = 0; i <= s1.length(); i++) {
  8.             for (int j = 0; j <= s2.length(); j++) {
  9.                 if (i == 0 && j == 0) {
  10.                     dp[i][j] = true;
  11.                 } else if (i == 0) {
  12.                     dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
  13.                 } else if (j == 0) {
  14.                     dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i - 1);
  15.                 } else {
  16.                     dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1) || dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
  17.                 }
  18.             }
  19.         }
  21.         return dp[s1.length()][s2.length()];
  22.     }
  23. }