• 困难
  • 中等
  • 简单

    题目描述

    给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

    来源，leetcode 每日一题 97. 交错字符串

image.png
示例：
97. 交错字符串 - 图2

  1. 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
  2. 输出：true
  4. 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
  5. 输出：false
  7. 输入：s1 = "", s2 = "", s3 = ""
  8. 输出：true

解题思路

  1. S3是有S1和S2组成，那么思路就可以如下：
    1. s3的前k个字符，可否由s1的前i个字符和s2的前j个字符交错而成？
    2. 使用动态规划：由于这里涉及到了s1和s2，那么就需要用二维数组，每个纬度分别表示s1或者s2，则动态转移方程为：
      1. result[i][j] = result[i-1][j] if s1[i] == s3[k] 或者
      2. result[i][j] = result[i][j-1] if s2[j] == s3[k]

        代码

        1. class Solution {
        2. public:
        3. bool isInterleave(string s1, string s2, string s3) {
        4. if (s3.length() != s1.length() + s2.length()) {
        5.    return false;
        6. } else if (s3.find(s1) != s3.npos && s3.find(s2) != s3.npos) {
        7.    return true;
        8. }
        9. int length1 = s1.length();
        10. int length2 = s2.length();
        11. vector<vector<bool>> result(s1.length() + 1,vector<bool>(s2.length() + 1));
        12. result[0][0] = true;
        13. for (int i = 0; i <= length1; i++) {
        14.    for (int j = 0; j <= length2; j++) {
        15.        int p = i + j - 1;
        16.        if (i > 0) {
        17.            result[i][j] = (result[i-1][j] && s1[i-1] == s3[p]) | result[i][j];
        18.        }
        19.        if (j > 0) {
        20.            result[i][j] = (result[i][j-1] && s2[j-1] == s3[p]) | result[i][j];
        21.        }
        22.        p++;
        23.    }
        24. }
        25. return result[length1][length2];
        26. }
        27. };

        总结

        什么时候会需要用动态规划？
        当问题可以按顺序进行解决的时候！