问题描述

给定三个字符串，判断第三个字符串是否能由前两个字符串的字符交替组合而成，且保持每个原字符串内部的字符顺序不变。

算法思路

使用动态规划解决该问题：

1. 状态定义：dp[i][j]表示第一个字符串的前$i$个字符和第二个字符串的前$j$个字符能否组成第三个字符串的前$i+j$个字符
2. 状态转移：
   • 若第一个字符串的第$i$个字符等于第三个字符串的第$i+j$个字符，则dp[i][j] |= dp[i-1][j]
   • 若第二个字符串的第$j$个字符等于第三个字符串的第$i+j$个字符，则dp[i][j] |= dp[i][j-1]
3. 边界条件：
   • dp[0][0] = true
   • 当第二个字符串为空时，完全匹配第一个字符串
   • 当第一个字符串为空时，完全匹配第二个字符串

   C++代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool isInterleave(string a, string b, string c) {
    int lenA = a.length(), lenB = b.length(), lenC = c.length();
    if (lenA + lenB != lenC) return false;

    vector<vector<bool>> dp(lenA + 1, vector<bool>(lenB + 1, false));
    dp[0][0] = true;

    // 初始化第一行（仅使用a的字符）
    for (int i = 1; i <= lenA; ++i)
        dp[i][0] = (a[i-1] == c[i-1]) && dp[i-1][0];

    // 初始化第一列（仅使用b的字符）
    for (int j = 1; j <= lenB; ++j)
        dp[0][j] = (b[j-1] == c[j-1]) && dp[0][j-1];

    // 填充DP表
    for (int i = 1; i <= lenA; ++i) {
        for (int j = 1; j <= lenB; ++j) {
            int pos = i + j - 1;
            bool fromA = (a[i-1] == c[pos]) && dp[i-1][j];
            bool fromB = (b[j-1] == c[pos]) && dp[i][j-1];
            dp[i][j] = fromA || fromB;
        }
    }

    return dp[lenA][lenB];
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        string a, b, c;
        cin >> a >> b >> c;
        cout << "Data set " << i << ": " << (isInterleave(a, b, c) ? "yes" : "no") << endl;
    }
    return 0;
}