※ 引述《a106a106 (猜猜我4誰)》之銘言： 我想到一個做法 但是不曉得有沒有漏洞 思路跟找palindrome的方式類似 從任何兩個連續的character i, i+1 開始往兩邊出發 合法的情況會有 yxxy,xxxx:左右各前進一步 yxxx:左邊暫停，右邊前進一步 xxxy:左邊前進一步，右邊暫停 如果以上都不符合，嘗試下一個i 測試了幾個case有過，有甚麼地方錯的嗎 bool eliminate(string s) { int len = (int) s.length(); if (len <= 1) return len == 0; for (int i = 0; i < len - 1; i++) { if (s[i] != s[i + 1]) continue; int j = i, k = i + 1; while (j >= 1 && k < len - 1) { if (s[j - 1] == s[k + 1]) { j--; k++; } while (j >= 1 && s[j] == s[j - 1]) j--; while (k < len - 1 && s[k] == s[k + 1]) k++; } if ((j < 0 || eliminate(s.substr(0, j))) && (k >= len || eliminate(s.substr(k + 1)) || eliminate(s.substr(k)))) return true; } return false; } 感謝推文指出錯誤 後來想了一下 yxxyxxy失敗的原因 yxxy處理完後xxy被當成無效的字串 但是yxxy的最後一個y其實可以和xxy合在一起 只要我們確定 [...]xxy 括弧裡面是可以完全消除的字串 另外也想了用DP該如何解 思路大概是這樣 vector<int> dp(s.length(), 0); for (int i = 1; i < s.length(); i++) { if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == s[i]) { dp[i] = dp[i - 1] + 2; dp[i] += ((i - dp[i - 1] - 2 >= 0) ? dp[i - dp[i - 1] - 2] : 0); } } 以yxxyxxy來作為例子 s=yxxyxxy dp=0024060 會發現這樣做不能處理最後一個y和第一個y結合的情況 還要再想一下怎麼做 目的是希望 dp[s.length()-1]==s.length() 來證明是可以完全消除的字串 : 題目：隨機給定一字串，判斷此字串最後能不能變成空字串 : 列出了很多組字串思考，原本是想找有aba或bab單獨存在的字串，但後來發現無論如何都會 : 有例外，一直找不到可以直接判斷的方法，想請問有沒有大大對這題有任何想法可以一起討 : 論，我想了好幾天都想不出來... : 謝謝大家QQQ : -- :

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.102.238 : ※ 文章網址: https://webptt.com/m.aspx?n=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: 就一直跑看會不會變空字串不就好了 09/21 14:17 : 推 s4300026: 我的想法是存入vector，用for，如果iter值跟下一個相同 09/21 14:48 : → s4300026: ，就再檢查下一個，直至不相同，然後刪除中間區塊，iter 09/21 14:48 : → s4300026: --，iter到底後檢查vector是否為空，結案。 值得思考的 09/21 14:48 : → s4300026: 是，有沒有特解是要先消後面一組的，而不能用貪心法解。 09/21 14:48 : → s4300026: 當我沒說，哈哈，你的例子，我的方法就無用了 09/21 14:49 : → sarafciel: 樓上的作法感覺先做一遍reverse後可以解? 09/21 15:10 : 推 a21802: 但是這個你的這個規律會因為消的順序不同有不同結果 09/21 17:03 : 推 cphe: 它應該就是只要找到一個順序可以全消就算吧 09/21 17:23 : → sarafciel: 樓樓上一講我才發現原PO給的例子好像兩個xx位移了XD 09/21 17:35 : → a106a106: 的確是，只要找到可以消完的方法就算可以，而消字串的 09/21 18:30 : → a106a106: 順序不需固定 09/21 18:30 : 目前有關於線性串列的想法，如果把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均取代 09/21 18:51 : → s4300026: 成X，直至無法取代，檢查無小寫字就過關。 09/21 18:51 : → s4300026: Y左右檢查不受大寫字影響 09/21 18:52 : 推 s4300026: 話說這應該去prob_solve 09/21 18:55 : 推 LPH66: 樓上一樣, 決定取代的順序會有差 09/21 19:51 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.140.223 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1537533041.A.319.html ※ 編輯: gofigure (111.240.84.199), 09/23/2018 11:45:30