→ idiont: yxxyxxy 09/22 03:22
→ gofigure: 嗯 while那邊應該可以改一下處理邊界問題 09/22 07:47
※ 編輯: gofigure (111.240.84.199), 09/23/2018 11:45:30
推 LPH66: 你的 DP 只會 +2 所以不會在 yxxyxxy 裡得到 7 09/23 15:34
→ LPH66: 我沒試跑, 不過以這樣看起來可能 yyy 也不會過 09/23 15:35
※ 引述《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://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: 就一直跑看會不會變空字串不就好了 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://www.ptt.cc/bbs/C_and_CPP/M.1537533041.A.319.html