题目链接

97. 交错字符串 - 力扣（LeetCode）

解答

递归回溯

        题目所述为两个字符串交替组成第三个字符串，之前好像做过相似的题目，直接联想到可以考虑使用递归回溯的做法，让字符串s1和字符串s2分别作为起始字符串，依次列举所有的情况，直至返回正确答案，或者回溯退出。

举例说明：如题目所言s1 = "aabcc"，s2 = "dbbca"，s3 = "aadbbcbcac"；

        若s1为起始字符串，s1[0] == s3[0]，此时下一位的情况可以为s1[1]或者s2[0]与s3[1]进行比较。

        若s2为起始字符串，由s2[0] != s3[0]，所以s2不能作为匹配成功，下一位的情况只能为s1[0]与s3[0]进行比较。

        参考代码如下：

class Solution {
    public int len1, len2, len3;
    public String s1, s2, s3;
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
        if(len1 + len2 != len3)   return false;
        this.len1 = len1;   this.len2 = len2;  this.len3 = len3;
        this.s1 = s1;       this.s2 = s2;      this.s3 = s3;
        return backTrack(0, 0, 0, 1) || backTrack(0, 0, 0, -1);
    }
    // flag作为标志位，为1时利用s1和s3进行匹配，为-1时利用s2与s3进行匹配
    public boolean backTrack(int i, int j, int k, int flag){
        if(i == len1 && j == len2 && k == len3) return true;
        if(flag == 1){
            // 要穷举所有的情况，所以从i下标遍历到和s3对应字符不想等为止
            for(int start = i; start < len1; start++){
                if(s1.charAt(start) != s3.charAt(k + start - i))    break;
                if(backTrack(start + 1, j, k + start + 1 - i, -flag))  return true;
            }
        }else if(flag == -1){
            for(int start = j; start < len2; start++){
                if(s2.charAt(start) != s3.charAt(k + start - j))    break;
                if(backTrack(i, start + 1, k + start + 1 - j, -flag))  return true;
            }
        }
        return false;
    }
}

         以上递归回溯做法存在问题，最后一个测试用例不能通过。查看题解后参考如下动态规划做法。

动态规划

        

        本体动态规划dp[i][j] 表示s1的前i个字符和s2的前j个字符是否可以组成s3的前i + j个字符。如果可以则dp[i][j] = true，否则dp[i][j]  = false。

        target 的每个字符都是从 s1（向下）或者 s2（向右）拿到的，所以只要判断是否存在这条 target 路径即可；

参考代码如下：

class Solution {
    public int len1, len2, len3;
    public String s1, s2, s3;
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
        if(len1 + len2 != len3)   return false;
        boolean dp[][] = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;
        for(int j = 1; j <= len2; j++){
            if(s2.charAt(j - 1) != s3.charAt(j - 1))    break;
            dp[0][j] = true;
        }
        for(int i = 1; i <= len1; i++){
            if(s1.charAt(i - 1) != s3.charAt(i - 1))    break;
            dp[i][0] = true;
        }
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                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));
            }
        }
        return dp[len1][len2];
    }
}