Re: [問題] C/C++字串處理問題

[alan23273850 (God of Computer Science)]

※ 引述《a106a106 (猜猜我4誰)》之銘言：
: 標題: [問題] C/C++字串處理問題
: 時間: Fri Sep 21 14:00:59 2018
: 最近練習時寫到一個題目
: 給一個只由兩個字元(x、y)組成的字串(不超過30字)
: 例：xxyxxyxyy
: 把字串內相同的字劃分成一組
: 變成：xx y xx y x yy，如此就有6個組
: 再把有兩個相同字以上的組刪除
: 例如：xxyxxyxyy→xxyxxyx→xxyyxxx→xxxxx→空字串
:
: 題目：隨機給定一字串，判斷此字串最後能不能變成空字串
:
: 列出了很多組字串思考，原本是想找有aba或bab單獨存在的字串，但後來發現無論如何都會
: 有例外，一直找不到可以直接判斷的方法，想請問有沒有大大對這題有任何想法可以一起討
: 論，我想了好幾天都想不出來...
:
: 謝謝大家QQQ
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.102.238
: ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1537509661.A.BCF.html

這題我用心想了一下其實不難，只要你對 DP 夠熟悉。我的方法如下：

1) 先將字串切割成不同單位的子字串，例 'xyyxxyxxx' >> 'x' 'yy' 'xx' 'y' 'xxx'，

   此時我們說這個字串有 5 個單位的子字串。

2) 開 dp[30][30] 表格使 dp[i][j] 紀錄從第 i 單位到第 j 單位的子字串可化簡成哪

   些，可以是單獨的 'x'、多重的 'x'、單獨的 'y'、多重的 'y'，四種結果。

3) 此時我們先從每個小單位開始，dp[0][0] = 單'x'、dp[1][1] = 多'y'、dp[2][2] =

   多'x'、dp[3][3] = 單'y'、dp[4][4] = 多'x'。

4) 接下來，我們試著將子字串的長度延伸一單位並思考如何遞迴地求出。以單獨的 'x'

   來說，dp[0][3] = 單'x' if dp[0][0] = 單'x' and dp[1][3] = 多'y' 或者

   dp[0][1] = 單'x' and dp[2][3] = 多'y' 或者

   dp[0][2] = 單'x' and dp[3][3] = 多'y' 或者

   dp[0][0] = 多'y' and dp[1][3] = 單'x' 或者

   dp[0][1] = 多'y' and dp[2][3] = 單'x' 或者

   dp[0][2] = 多'y' and dp[3][3] = 單'x' 或者

   如此一來只要每次延伸一單位並遞迴地填表，最後必可求出 dp[0][len-1] 的值。

*) 值得注意的是在本題設定下 多'x'、多'y' 與 empty string 等價，這點也要考慮

   進去，例如 多'y' + 單'x' >> 單'x'。這當然也會讓 dp[i][j] 出現多重的結果，

   例如 'xxyy' 可以是 多'x' 也可以是 多'y'，因此每個 entry 都要分別獨立地儲存

   這四種結果並記錄有沒有可能達成。要用 struct 太麻煩，如何使用 bitwise 運算

   簡化你的 coding 那就要看工程師本身的素養了。

*) 時間與空間複雜度皆為θ(n^2)，不因字串內容而改變。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.168.84.247
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1537783205.A.D06.html
※ 編輯: alan23273850 (1.168.84.247), 09/24/2018 18:05:34
推 LPH66: 我可以好奇一下這個 DP 法如何檢知 xyxxyx?
→ LPH66: 這個記法似乎無法記錄 "xyxx" 這個結果
推 LPH66: 噢, 好像知道這種會怎麼檢查了...會從 xx 往外延伸出去
剛剛已經通過 UVA judge https://goo.gl/DT5UUw 的驗證，另外 DP 那邊我有點寫錯，
應該要對每種子切割都嘗試過一遍，已修正在內文中。
※ 編輯: alan23273850 (140.112.4.192), 09/25/2018 11:12:45