Hoodlum1980's Technological Blog

題目鏈接：《1004: Anagrams by Stack》。

為了防止題目鏈接失效，將題目原文復制如下：

1004. Anagrams by Stack

作者: ZOJ 出題組;

 

單位: zoj;

How can anagrams result from sequences of stack operations? There are two sequences of stack operators which can convert TROT to TORT:

[
i i i i o o o o
i o i i o o i o
]

where i stands for Push and o stands for Pop. Your program should, given pairs of words produce sequences of stack operations which convert the first word to the second.

Input Specification:

The input will consist of several lines of input. The first line of each pair of input lines is to be considered as a source word (which does not include the end-of-line character). The second line (again, not including the end-of-line character) of each pair is a target word. The end of input is marked by end of file.

Output Specification:

For each input pair, your program should produce a sorted list of valid sequences of i and o which produce the target word from the source word. Each list should be delimited by

[
]

and the sequences should be printed in "dictionary order". Within each sequence, each i and o is followed by a single space and each sequence is terminated by a new line.

Process

A stack is a data storage and retrieval structure permitting two operations:

• Push - to insert an item and
• Pop - to retrieve the most recently pushed item

We will use the symbol i (in) for push and o (out) for pop operations for an initially empty stack of characters. Given an input word, some sequences of push and pop operations are valid in that every character of the word is both pushed and popped, and furthermore, no attempt is ever made to pop the empty stack. For example, if the word FOO is input, then the sequence:

Sequence	Explanation
i i o i o o	is valid, but
i i o	is not (it's too short), neither is
i i o o o i	(there's an illegal pop of an empty stack)

Valid sequences yield rearrangements of the letters in an input word. For example, the input word FOO and the sequence i i o i o o produce the anagram OOF. So also would the sequence i i i o o o. You are to write a program to input pairs of words and output all the valid sequences of i and o which will produce the second member of each pair from the first.

Sample Input:

madam
adamm
bahama
bahama
long
short
eric
rice

Sample Output:

[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
]

代碼長度限制

32 KB

時間限制

2000 ms

內存限制

64 MB

棧限制

8192 KB

• 題意：

通過棧完成回文字符串：給定兩個單詞 word1 和 word2，假設有一個字符棧（stack），通過對字符的棧操作（i 為 push 入棧操作，o 為 pop 出棧操作），可能把 word1 轉變為 word2，那么這一系列的棧操作（由字母 i 和 o 組成）就是一個可行的操作。題目要求輸出所有可以完成把 w1 轉變為 w2 的操作，并按照字典順序輸出它們。

例如把 "TROT" 轉變為 "TORT"，則以下兩種操作序列，都可以做到：

• 分析：

這是一個困擾了我很多年的問題，從我最開始做 ZOJ 題目開始，就遇到這個問題，雖然這個題目看起來好像非常的簡單，但我常年來一直沒想到一個比較好的解題辦法，所以這道題一直擱置，但是它一直在我的心理。表面上看這道題有子問題，很類似動態規劃類題目，但是因為它每個子問題都有多組解，所以常規的解決動態規劃問題使用的二維矩陣那種存儲解的方法又并不合適。用窮舉法，顯然也不合適。所以我想來想去還是沒想好這個題目的做法。直到昨天，我決定去做一下這道題。

題意里講到的棧操作本身是非常直觀的，大家都知道棧具有 FILO （先進后出）的特點，所以我們把一個字符 push 到棧中以后，可以稍后再 pop 出，這就實現了把一個字符“稍晚”再輸出的效果，也就是相當于能把一個字符和它后面的多個字符，顛倒它們之間的順序（假設我們不 care 后面的多個字符之間的排列）。比如說，假如有一個字符 a 位于單詞 word1 的第一個字符，轉換后我們讓 a 位于單詞 word2 的最后一個字符：

　　word1: a[xxxx...]

　　word2: [xxxx...]a

對于這樣兩個單詞，可以用 "i [......] o" 這樣的操作（[......] 是對后面多個字符的合法棧操作序列，并能將這些字符全部輸出）達到讓 a 出現在它后面 n 個字符的后面的輸出結果。當然，[xxxx...] 這多個字符之間可能會順序比較混亂，目前我們不在意這一點。這樣，我們就可以令 a 和它后面的多個字符顛倒順序，讓 a 出現在輸出單詞的最后面。

不難得出結論：有且僅有 "i [ ... ] o" 這一種操作，可以讓長度為 len 的 word1 的首個字符出現在 word2 的結尾位置。其中：[ ... ] 是對 (len - 1) 個字符的任一合法棧操作序列。

對 n 個字符的合法棧操作序列，是指對連續的 n 個字符中的每個字符都入棧和出棧過一次，且所有操作合法，操作后 stack 棧頂指針的指向位置和執行該操作序列之前相同。也就是說，該操作序列會把 n 個字符進行重新排列并產生一個新的 n 個字符的輸出結果。

這一點很重要，有了這個基本結論，就可以開始把原問題拆解為規模更小的子問題。

我們在 word2 中逐個字符檢查，看它是不是 word1 的首個字符，如果在 word2 的某個位置的字符，是 word1 的首個字符，那么問題將會分解為如下：

因此解決該問題的方法是：從 word2 的第一個字符開始，遍歷 word2 的每個字符，如果 word2 的 i-th (0-based) 字符和 word1 的首字符（假設為 a）相同，那么在索引為 i 的位置，就可以把原問題分解為兩個子問題：

1. word1 中位于 a 后面的 i 個字符，如何通過合法棧操作，轉變為 word2 中的前 i 個字符。
2. word1 中尾部的 (len - i - 1) 個字符，如何通過合法棧操作，轉變為 word2 中的尾部的 （len - i - 1) 個字符。

如果有了以上的子問題的解，就可以得出當前問題的一組解：把  a 入棧，加上子問題（1）的解，把 a 出棧，加上子問題（2）的解，就是當前問題的解。

如果把子問題（1）的解集 (注意：包含多個解)，稱為 child1，把子問題（2）的解集 (注意：包含多個解)，稱為 child2，那么當前問題的解將會增加 child1.size() * child2.size() 個。可以把新增加的這些解，表示為：

當然，前提是子問題（1）和（2）必須都有解。可以看出，子問題（1）和（2）和當前問題屬于本質相同的問題，這啟發我們可以使用遞歸函數來解決這個問題。

首先，定義解決問題的遞歸函數的原型如下：

typedef struct tagSTR
{
    char x[256];
} STR, *PSTR;

//把 word1 通過棧操作轉換為 word2，所有可能的操作序列，被存儲在 results 中。
//[in]  const char* word1: 第一個單詞。
//[in]  const char* word2: 第二個單詞，長度和 word1 相同。
//[in]  int len: word1 和 word2 包含的字符數量 (strlen)。
//[out] std::vector<STR> &results: 存儲從 word1 轉換到 word2 的所有棧操作序列。
//返回值: bool 是否有解。返回值 = !results.empty();
bool Convert(const char* word1, const char* word2, int len, std::vector<STR> &results);

然后，定義規模最小問題的解（回歸條件），為了求解代碼的一致性和簡潔性，對問題邊界做以下定義：

1. 當 len = 0 時，有一個解：長度為 0 的空字符串（注：非 NULL 值）。
2. 當 len = 1 時，如果兩個單詞的首字符相同，則有一個解：io，否則問題無解。

在函數返回時，通過判斷 results.empty() 的值也可以判斷問題是否有解，results 為空集合則無解。

如果任何一個子問題無解，則在當前索引 i 的位置無解，繼續檢查 word2 的下一個字符。當找到所有解后，再對包含所有解的容器做一次按升序排序即可。

• 用于提交的代碼：

#include <vector>
#include <algorithm>

typedef struct tagSTR
{
    char x[256];
} STR, *PSTR;

//判斷兩個元素是否已經是“有序”排列。（從小到大排序）
bool ASC(STR s1, STR s2);


//把 word1 通過 stack 操作轉換為 word2，操作序列存儲在 results 中。
//
//[in]  const char* word1: 第一個單詞。
//[in]  const char* word2: 第二個單詞。
//[in]  int len: word1 和 word2 的長度 (strlen)。
//[out] std::vector<STR> &results: 存儲從 word1 轉換到 word2 的所有操作。
//[return] bool: 是否有解。

bool Convert(const char* word1, const char* word2, int len, std::vector<STR> &results);


int main(int argc, char* argv[])
{
    std::vector<STR> results;
    std::vector<STR>::const_iterator it;
    int len1, len2;
    char word1[256], word2[256];

    while(fgets(word1, sizeof(word1), stdin) != NULL)
    {
        //trim '\r' or '\n' char;
        len1 = (int)strlen(word1);
        if(len1 && (word1[len1 - 1] == '\r' || word1[len1 - 1] == '\n'))
        {
            word1[len1 - 1] = 0;
            len1--;
        }

        word2[0] = 0;
        fgets(word2, sizeof(word2), stdin);

        //trim '\r' or '\n' char;
        len2 = (int)strlen(word2);
        if(len2 && (word2[len2 - 1] == '\r' || word2[len2 - 1] == '\n'))
        {
            word2[len2 - 1] = 0;
            len2--;
        }

        results.clear();
        if(len1 == len2)
        {
            Convert(word1, word2, len1, results);
            std::sort(results.begin(), results.end(), ASC);
        }

        //output
        printf("[\n");
        for(it = results.begin(); it != results.end(); ++it)
        {
            const char *p1 = it->x;
            while(*p1)
            {
                printf("%c ", *p1);
                ++p1;
            }
            printf("\n");
        }
        printf("]\n");
    }
    return 0;
}


//User-defined predicate function object that defines the comparison
//criterion to be satisfied by successive elements in the ordering. 
//A binary predicate takes two arguments and returns true when satisfied
//and false when not satisfied.

bool ASC(STR s1, STR s2)
{
   return strcmp(s1.x, s2.x) <= 0;
}

bool Convert(const char* word1, const char* word2, int len, std::vector<STR> &results)
{
    std::vector<STR> child1; //子問題 (1) 的解。
    std::vector<STR> child2; //子問題 (2) 的解。
    std::vector<STR>::const_iterator it1, it2;
    STR item;
    int i;

    if(len == 0)
    {
        //放入一個空字符串。
        item.x[0] = 0;
        results.push_back(item);
        return true;
    }
    else if(len == 1)
    {
        if(word1[0] == word2[0])
        {
            strcpy(item.x, "io");
            results.push_back(item);
        }
        return results.size() != 0;
    }

    //when len > 1;
    for(i = 0; i < len; i++)
    {
        // index:  0      i     len-1
        //         |      |      |
        //        [a][x1...][x2...]
        //        [y1...][a][y2...]
        // result: [i  child1  o] * [child2];

        if(word1[0] == word2[i])
        {
            child1.clear();
            Convert(word1 + 1, word2, i, child1);
            if(child1.empty())
                continue;
            
            child2.clear();
            Convert(word1 + i + 1, word2 + i + 1, len - i - 1, child2);
            if(child2.empty())
                continue;

            //解: [i child1 o] * [child2]
            for(it1 = child1.begin(); it1 != child1.end(); ++it1)
            {
                for(it2 = child2.begin(); it2 != child2.end(); ++it2)
                {
                    sprintf(item.x, "i%so%s", it1->x, it2->x);
                    results.push_back(item);
                }
            }
        }
    }
    return results.size() != 0;
}

solution code

• 總結：

很遺憾的就是，由于時隔多年，ZOJ 網站也早就移交給其他網站托管，新的網址不知何故，我沒法提交代碼，所以不知道上面的代碼能否 AC。不過對于所有題目給出的示范輸入，程序輸出都是正確的。希望我已經解決了這個困擾我十多年的一道題目。把代碼整理一下以后，最后代碼是非常簡短的，只有很少的行數，沒想到困擾我十多年的問題，就在那天晚上突然冒出來再嘗試做一次的想法，只嘗試一個晚上就大概做出來了，而且最后的代碼量是很少的。最終，是使用遞歸函數來解決問題，方法并不困難，難點在于，找到把原問題分解成同一類子問題的切入點，使用動態規劃算法的問題也是如此。

對于解決具有同類子問題的問題，我們可以想到使用遞歸函數，遞歸函數是一個強大的工具，可以解決這種具有同類子問題的問題，但是遞歸函數也有缺點：如果遞歸函數的遞推深度太深，對線程棧會有壓力，會有 ”爆棧“ （Stack Overflow）的風險。要降低這種風險，可以考慮：

（1）減少遞推深度（但是這個是由問題本身決定的，所以通常我們很難控制遞推深度）。

（2）減小遞歸函數的棧上空間需求，例如，可以把一些較大的臨時對象（例如數組），改為在堆上分配，就可以減小每一層遞歸函數對棧空間的需求。

（3）改寫算法，借助用戶自定義的棧，把遞歸函數改寫為非遞歸函數，相當于把記錄和存儲函數執行上下文的功能，從線程棧，轉交給用戶自定義的棧，而用戶自定義棧的容量是可以很大的，這樣就可以不受線程棧的空間限制。

• 附: 本博文質量（作者自評）