好的，下面是对上述代码的详细介绍，包括每部分的功能和实现逻辑。

代码结构

  1. 类定义：我们定义了一个 Solution 类，其中包含一个成员函数 isInterleave，用于判断字符串是否可以交织。
  2. 主函数：在 main 函数中，我们实例化 Solution 类并测试了几个示例用例。

主要功能函数：isInterleave

bool isInterleave(std::string s1, std::string s2, std::string s3) {
  • 参数： s1：第一个输入字符串。s2：第二个输入字符串。s3：需要检查的目标字符串，是否能由 s1 和 s2 交织而成。

检查长度

if (m + n != s3.size()) {
    return false;
}
  • 首先计算 s1 和 s2 的长度之和 m + n，如果与 s3 的长度不一致，直接返回 false。因为交织的字符串必须具有相同的总长度。

初始化 DP 表

std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));
dp[0][0] = true; // 两个空字符串可以交织成一个空字符串
  • 创建一个二维布尔数组 dp，其大小为 (m + 1) x (n + 1)，初始值全部为 false。这个数组用于记录状态。
  • dp[i][j] 表示 s3 的前 i + j 个字符是否可以由 s1 的前 i 个字符和 s2 的前 j 个字符交织而成。
  • dp[0][0] 被设置为 true，表示两个空字符串可以交织成一个空字符串。

填充 DP 表

for (int i = 0; i <= m; ++i) {
    for (int j = 0; j <= n; ++j) {
        if (i > 0 && s1[i - 1] == s3[i + j - 1]) {
            dp[i][j] = dp[i][j] || dp[i - 1][j];
        }
        if (j > 0 && s2[j - 1] == s3[i + j - 1]) {
            dp[i][j] = dp[i][j] || dp[i][j - 1];
        }
    }
}
  • 使用双重循环遍历 dp 数组的所有元素。
  • 对于每个 dp[i][j]： 如果 s1 当前字符（s1[i - 1]）与 s3 的当前字符（s3[i + j - 1]）相等，并且前一个状态 dp[i - 1][j] 为 true，则更新 dp[i][j] 为 true。同样地，如果 s2 当前字符（s2[j - 1]）与 s3 的当前字符相等，并且前一个状态 dp[i][j - 1] 为 true，也更新 dp[i][j]。

返回结果

return dp[m][n];
  • 最后返回 dp[m][n]，这是整个算法的核心结果，表示完整的 s1 和 s2 是否可以交织成 s3。

示例用法

int main() {
    Solution sol;

    std::string s1 = "xxyzz";
    std::string s2 = "pyyzx";
    std::string s3_1 = "xxpyyzyzxz"; // 应该返回 true
    std::string s3_2 = "xxpyyyxzzz"; // 应该返回 false

    std::cout << std::boolalpha;
    std::cout << "Test case 1: " << sol.isInterleave(s1, s2, s3_1) << std::endl; // 输出: true
    std::cout << "Test case 2: " << sol.isInterleave(s1, s2, s3_2) << std::endl; // 输出: false

    return 0;
}
  • 在 main 函数中，首先创建一个 Solution 对象 sol。
  • 定义了两个字符串 s1 和 s2，以及两个测试用的 s3 字符串。
  • 使用 std::cout 输出结果，通过调用 isInterleave 方法来判断每个 s3 是否可以由 s1 和 s2 交织而成。

总结

  • 该算法利用动态规划有效地解决了交织字符串的问题。
  • 时间复杂度为 O(m * n)，空间复杂度也是 O(m * n)，适合中等规模的字符串交织判断。