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

看板C_and_CPP作者alan23273850 (God of Computer Science)時間7年前 (2018/09/24 18:00)推噓2(2推 0噓 1→)

留言3則, 1人參與討論串3/3 (看更多)

※ 引述《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

09/24 22:15, 7年前 , 1^F

09/24 22:15, 1^F

→

LPH66

09/24 22:16, 7年前 , 2^F

09/24 22:16, 2^F

推

LPH66

09/24 22:27, 7年前 , 3^F

09/24 22:27, 3^F