ACM 1004 Anagrams by Stack - DFS 經典題解

ZOJ 1004 Anagrams by Stack 題解：棧排列生成與 DFS 回溯

本題給定兩個等長字符串 source 和 target，模擬棧操作：每步可選 i (入棧，讀取 source 下一字符) 或 o (出棧，寫入輸出)，要求輸出序列等於 target。輸出所有合法操作序列 (字典序)。

問題建模

• 輸入指標 in (0..n)，輸出指標 out (0..n)，棧頂指標 top (0..n)
• 狀態合法條件：out ≤ in ≤ n，top = in - out
• 操作 i：in < n 時可執行，stack[top++] = source[in++]
• 操作 o：top > 0 且 stack[top-1] == target[out] 時可執行，out++, top--
• 終止條件：in == n && out == n，輸出當前操作序列

DFS 遞歸實現

#include 
#include 

char source[100], target[100], stack[100], ops[200];
int n;

void dfs(int in, int out, int top, int op_len) {
    if (in == n && out == n) {
        ops[op_len] = '\0';
        for (int i = 0; i < op_len; i++) putchar(ops[i]), putchar(' ');
        putchar('\n');
        return;
    }
    // 嘗試 'i' (入棧) - 字典序優先
    if (in < n) {
        stack[top] = source[in];
        ops[op_len] = 'i';
        dfs(in + 1, out, top + 1, op_len + 1);
    }
    // 嘗試 'o' (出棧)
    if (top > 0 && out < n && stack[top - 1] == target[out]) {
        ops[op_len] = 'o';
        dfs(in, out + 1, top - 1, op_len + 1);
    }
}

int main() {
    while (scanf("%s %s", source, target) == 2) {
        n = strlen(source);
        printf("[\n");
        if (n == strlen(target)) dfs(0, 0, 0, 0);
        printf("]\n");
    }
    return 0;
}

關鍵點解析

1. 字典序輸出：先嘗試 i 再嘗試 o，自然產生字典序遞增的操作序列
2. 剪枝條件：出棧前必須檢查棧頂字符匹配 target[out]，大幅減少搜索空間
3. 棧模擬：用陣列 stack + top 模擬，避免 STL stack 開銷
4. 輸出格式：每個操作字符後跟空格，整體包裹在 [] 中，每行一個序列

複雜度分析

• 最壞情況 (如全相同字符) 合法序列數為第 n 個 Catalan 數 C_n = (2n)!/(n!(n+1)!)
• 時間複雜度 O(C_n * n)，空間 O(n) (遞歸深度 + 棧 + 操作序列)
• n ≤ 100 但實際測試數據較小，DFS 可在時限內通過

常見錯誤

1. 未檢查 stack[top-1] == target[out] 直接出棧，產生大量無效序列導致 TLE
2. 輸出格式錯誤：缺少空格、方括號位置、換行處理
3. 未處理多組測試輸入直到 EOF
4. 遞歸深度過大導致棧溢出 (可改用手動棧模擬遞歸)

擴展思考

若 target 包含重複字符，剪枝條件 stack[top-1] == target[out] 依然正確，因為棧頂字符由先前的入棧順序唯一決定，匹配即為唯一合法出棧選擇。