主題

ZeroJudge - e685: 00732 - Anagrams by Stack　解題心得

Not In My Back Yard | 2020-02-27 00:24:42 | 巴幣 0 | 人氣 213

題目連結：

e685: 00732 - Anagrams by Stack

題目大意：

輸入有多筆測資，每筆佔兩列。測資第一列給定一字串，代表原始字串；第二列給定另一字串，代表目標字串。請求出使用堆疊（Stack）的操作，使得原始字串重組變成目標字串的所有方法。

例如 TROT 變成 TORT 有以下兩種方式：

[

i i i i o o o o

i o i i o o i o

]

其中 i 代表放入堆疊（Push）、o 代表從堆疊頂端移出元素（Pop）。

每組測資的方法分別用一列「[」以及一列「]」將其標記出來，且所有方法請依照字典序由小到大排序。輸出格式參見範例輸出。

範例輸入：

madam

adamm

bahama

long

short

eric

rice

範例輸出：

[

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

]

解題思維：

首先，如果兩個字串長度不一樣或是內容組成不一樣，那就可以直接輸出單獨的一列「[」和「]」了。因為一定不會有任何方法使原始字串變為目標字串。

其他的就是窮舉每一步可不可以放 i 或是 o 。但是單純這樣窮舉是 2 ^ L （L 是字串的長度）。所以需要作一些判斷，避免做不必要的事。例如當目前堆疊頂端的字元不符合目前要匹配到的目標字串之字元，則當然不能執行 o 的步驟。

本人的程式碼（於 CodePile 上）

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。

#程式題目解題心得 #深度優先搜尋（Depth First Search）#窮舉

留言

創作回應

第三方訪客

你好，想請問，紀錄newword的用意是甚麼，然後再回傳到buf又是因為甚麼，看起來是因為有newword才可以找出下一個方法，但不知道為甚麼這樣子就可以輕鬆找出來

2021-10-19 14:49:56

Not In My Back Yard

程式碼裡面的 "buffer" 是充當堆疊的角色，也就是題目提及的那個堆疊。而 newWord 是記錄當前堆疊元素進出的方式而產生的「新」字詞。

例如原字串為 TROT，而現在窮舉到的進出方式為 i i i i o o o，則 newWord 裡面的內容將會是 "TOR"。

基本上就是真的去模擬題目的要求，而我們為了可以得到目標字串而窮舉出所有可能的進出方式。

2021-10-19 15:50:53

第三方訪客

應該說，如果是第一次，找出第一種方法我懂，但我不知為甚麼，在印出 o的時候要把字先存到 newword裡 (newword應該是跟target string一樣吧?)(這邊我懂了就是上面說的，紀錄堆疊造成的新字詞)
然後後面找到一個方法後，再從 newword(新字詞)裡一個一個丟回去，就又能找到新方法了這是我不懂的地方
因為我可能想得比較簡單，我只覺得在第二個if，利用原字串去堆疊，才是真正的方法因為在way裡面有新加入'i'，但在第三個if，最後一行利用newWord，再丟回去堆疊時，way就沒有新加入'i'了，這次的堆疊不算一次輸入嗎，這是我疑惑的地方

2021-10-19 17:41:38

Not In My Back Yard

我覺得應該是我程式碼寫得看起來很奇怪（畢竟我把本來遞迴會當參數傳的全部變成全域變數然後自己去模擬遞迴參數的變化）

因此我額外寫了另一個純遞迴參數（除了 start 和 target 字串）版本，如下
http://codepad.org/o39m4uwk

此外我不是很懂「最後一行利用newWord，再丟回去堆疊時，way就沒有新加入'i'了，這次的堆疊不算一次輸入嗎」這段是在問什麼。我自己是真的覺得應該是我自己模擬遞迴參數的關係，所以你可能沒意會 topPointer 、 wordPointer 的變化之類的？

總之你可以先看上面新的程式碼試試看，也許就通了。

2021-10-19 18:07:14

Not In My Back Yard

抱歉遞迴部分的排版有點跑掉了，可以看這邊的
http://codepad.org/xuiBldJI
也可以你複製下來自己重新排XD

2021-10-19 18:08:51

第三方訪客

QQ，我想我知道我的問題是甚麼了，就是newWord的用意，感覺不到它能怎麼實際去影響這個程式，就是紀錄完新詞之後，我該怎麼去使用他，感覺是我遞迴很爛 0.0

2021-10-19 20:38:28

Not In My Back Yard

突然發現寫成參數版本後，newWord 就再也沒有任何用處了，所以可以刪除。

我猜你的疑問是：原本遞迴可以不需要 newWord，但是我原本的程式碼卻有著這個東西。而因為我的原始版本程式是模擬遞迴參數變化，而原先充當字元堆疊的 buffer 在從遞迴回來後需要復原的資訊如果不儲存下來便會遺失。此時 newWord 便派上了用場。

說實話，有別的做法可以讓 newWord 完全不出現（例如你直接在第三個 if 宣告一個變數來儲存 buffer 的最後一個字元），可是這對於 debug 會是一個好用的指標性輸出，因為你可以知道每一層現在在幹嘛、目前產生了什麼詞。

2021-10-19 22:05:03

Not In My Back Yard

而如果題目如果是「使用堆疊可以產生的所有字詞」，則此時 newWord 就是必要的。所以在這題就是本人當初的寫程式之習慣所造成的令人誤解之處。在此說聲抱歉。

2021-10-19 22:08:43

第三方訪客

我看懂了，真的很感謝你!

2021-10-20 19:51:21

Not In My Back Yard

很高興可以解開你的疑惑。如果我的別篇心得也有一些怪異或是邏輯不順之處也歡迎提出。

2021-10-20 20:30:30