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

[a106a106 (猜猜我4誰)]

最近練習時寫到一個題目
給一個只由兩個字元(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
※ 編輯: a106a106 (27.242.102.238), 09/21/2018 14:05:06
※ 編輯: a106a106 (27.242.102.238), 09/21/2018 14:08:32
→ MOONRAKER: 就一直跑看會不會變空字串不就好了
推 s4300026: 我的想法是存入vector，用for，如果iter值跟下一個相同
→ s4300026: ，就再檢查下一個，直至不相同，然後刪除中間區塊，iter
→ s4300026: --，iter到底後檢查vector是否為空，結案。 值得思考的
→ s4300026: 是，有沒有特解是要先消後面一組的，而不能用貪心法解。
→ s4300026: 當我沒說，哈哈，你的例子，我的方法就無用了
→ sarafciel: 樓上的作法感覺先做一遍reverse後可以解?
推 a21802: 但是這個你的這個規律會因為消的順序不同有不同結果
推 cphe: 它應該就是只要找到一個順序可以全消就算吧
→ sarafciel: 樓樓上一講我才發現原PO給的例子好像兩個xx位移了XD
→ a106a106: 的確是，只要找到可以消完的方法就算可以，而消字串的
→ a106a106: 順序不需固定
目前有關於線性串列的想法，如果把xyxxxyyx轉成陣列{1, 1, 3, 2, 1}的表示，如果把中
間3個x刪掉後就變成{1, (1+2), 1}，再刪掉3個y變成{2}，即可成為空字串。
問題是消除的順序有很多種可能，目前我找不到完美的公式可以解決的
※ 編輯: a106a106 (27.242.102.238), 09/21/2018 18:36:09
推 s4300026: 那我想到第二種做法，Y取代yy，Y左右都是x，則x均取代
→ s4300026: 成X，直至無法取代，檢查無小寫字就過關。
→ s4300026: Y左右檢查不受大寫字影響
推 s4300026: 話說這應該去prob_solve
推 LPH66: 樓上一樣, 決定取代的順序會有差
→ longlongint: 用 stack
→ longlongint: 哦 原來刪的順序有差 QQ
推 oToToT: 感覺這不是要發在prob_solve嗎？
推 scott870430: 檢查左右是不是相同字元
→ scott870430: 是的話優先消掉?
推 alan23273850: 這題應該可以用 DP，我有空發文
→ alan23273850: 想順便問大大那題的 judge 在哪，想先確定無 bug
推 vnon: https://i.imgur.com/WYIVLpM.png 能走回中間=>可變成空字串
→ vnon: https://pastebin.com/SjiDRPjC 用上面的想法通過題目了
推 alan23273850: 樓上水喔～