交错字符串

题目链接

交错字符串

题目描述

注意点

• s1、s2、和 s3 都由小写英文字母组成
• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• 能否仅使用 O(s2.length) 额外的内存空间来解决它

解答思路

• 最初想到的是使用深度优先遍历，使用指针指向当前s3需要的字符、当前能取s1和s2的相应字符，如果都不是s3需要的字符，则说明当前情况不满足题意，否则需要取s1或s2中满足的字符并移动指针继续进行深度优先遍历。但是该方法时间复杂度不满足
• 参考题解使用动态规划解决本题，思路为：使用二维数组dp存储是否是交错字符串，dp[i][j]表示s1中取前i个字符（即0~i - 1），s2中取前j个字符（即0~j - 1）能否交错组成s3中前i + j个字符，dp[s1.length()][s2.length()]代表的就是整个s1和整个s2能否交错组成s3，也就是本题的答案
• dp[i][j]怎么由前面的dp推算出来？首先dp[0][0]一定满足题意（空字符串可以组成空字符串），dp[i][j]是否满足取决于以下两种情况：
  • 如果i大于0，其可以由dp[i - 1][j]是否满足、s1的第i个字符与s3的第i + j个字符是否相同决定
  • 如果j大于0，其可以由dp[i][j - 1]是否满足、s2的第j个字符与s3的第i + j个字符是否相同决定

代码

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n1 = s1.length();
        int n2 = s2.length();
        int n3 = s3.length();
        if (n1 + n2 != n3) {
            return false;
        }
        // dp[i][j]代表s1的前i个元素与s2的前j个元素能否组成s3的前i + j个字符
        boolean[][] dp = new boolean[n1 + 1][n2 + 1];
        dp[0][0] = true;
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                if (i > 0 && dp[i - 1][j]) {
                    dp[i][j] = dp[i][j] || s1.charAt(i - 1) == s3.charAt(i + j - 1);
                }
                if (j > 0 && dp[i][j - 1]) {
                    dp[i][j] = dp[i][j] || s2.charAt(j - 1) == s3.charAt(i + j - 1);
                }
            }
        }
        return dp[n1][n2];
    }
}

关键点

• 动态规划的思想
• 注意边界问题
• 当dp[i][j]既能由i - 1又能由j - 1决定时，只要其中一个满足交错字符串dp[i][j]就满足