HDOJ 1501 Zipper 解題報告：DFS 判斷字符串交織

問題描述

給定三個字符串 A、B、C，判斷 C 是否可以由 A 和 B 的字符交織而成。交織規則：A 和 B 的字符順序必須保持不變，但可以任意交替選取。例如 A="cat"，B="tree"，C="tcraete" 可行；C="catrtee" 也可行；但 C="cttaree" 不行。

輸入格式

第一行為測試數據組數 T (1~1000)。每組數據一行，包含三個由空格分隔的字符串，僅含大小寫字母。第三個字符串長度等於前兩者長度之和，前兩字符串長度 1~200。

輸出格式

每組輸出 "Data set n: yes" 或 "Data set n: no"，n 為數據編號。

解題思路：深度優先搜索 (DFS)

使用遞歸函數 dfs(i, j, k) 表示 A 已匹配到第 i 個字符，B 已匹配到第 j 個字符，C 已匹配到第 k 個字符。若 k == len(C) 則成功。否則嘗試從 A 或 B 取下一字符匹配 C[k]，若匹配則遞歸。為避免重複狀態，可用 vis[i][j] 標記。

代碼實現 (C/C++)

#include <cstdio>
#include <cstring>
using namespace std;

char str1[205], str2[205], str[405];
int vis[205][205];
int len1, len2, len;
int flag;

void dfs(int a, int b, int l) {
    if (vis[a][b]) return;
    if (a == len1 && b == len2) { flag = 1; return; }
    if (flag) return;
    vis[a][b] = 1;
    if (str[l] == str1[a] && a < len1) dfs(a + 1, b, l + 1);
    if (str[l] == str2[b] && b < len2) dfs(a, b + 1, l + 1);
}

int main() {
    int t; scanf("%d", &t);
    for (int cs = 1; cs <= t; ++cs) {
        scanf("%s %s %s", str1, str2, str);
        len1 = strlen(str1); len2 = strlen(str2); len = strlen(str);
        memset(vis, 0, sizeof(vis));
        flag = 0;
        if (str1[len1-1] == str[len-1] || str2[len2-1] == str[len-1])
            dfs(0, 0, 0);
        printf("Data set %d: %s\n", cs, flag ? "yes" : "no");
    }
    return 0;
}

複雜度分析

狀態數最多 (len1+1)*(len2+1) ≤ 201*201 ≈ 4萬，每狀態 O(1) 轉移，總時間 O(len1*len2)，空間 O(len1*len2)，完全滿足限制。

關鍵點總結

• DFS + 記憶化搜索避免重複計算
• 先檢查最後一字符是否匹配，可提前剪枝
• 注意輸入可能包含大小寫，直接按字符比較即可