题解 | #交织子序列#

测试用例不全，下面的错误代码也能A

import java.util.*;


public class Solution {

    public boolean isInterleave (String s, String x, String t) {
        int sIndex = s.length() - 1;
        int xIndex = x.length() - 1;
        int tIndex = t.length() - 1;

        while (tIndex >= 0 && sIndex >= 0 && xIndex >= 0) {
            if (t.charAt(tIndex) == s.charAt(sIndex)) {
                tIndex--;
                sIndex--;
            } else if (t.charAt(tIndex) == x.charAt(xIndex)) {
                tIndex--;
                xIndex--;
            } else {
                return false;
            }
        }

        return true;
    }
}

这题用动态规划才是正解

import java.util.*;


public class Solution {

    public boolean isInterleave (String s, String x, String t) {
        if (s.length() + x.length() != t.length()) return false;

        // dp[i][j] 表示字符串 s 的前 i 个字符和字符串 x 的前 j 个字符能否组成字符串 t 的前 i+j 个字符的交织子序列。
        boolean[][] dp = new boolean[s.length() + 1][x.length() + 1];

        // 初始化dp数组
        dp[0][0] = true;
        for (int i = 1; i <= s.length(); i++) {
            dp[i][0] = (s.charAt(i - 1) == t.charAt(i - 1)) && dp[i - 1][0];
        }
        for (int i = 1; i <= x.length(); i++) {
            dp[0][i] = (x.charAt(i - 1) == t.charAt(i - 1)) && dp[0][i - 1];
        }

        // dp start
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= x.length(); j++) {
                if ((s.charAt(i - 1) == t.charAt(i + j - 1)) && dp[i - 1][j] ||
                        x.charAt(j - 1) == t.charAt(i + j - 1) && dp[i][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[s.length()][x.length()];
    }
}