前往
大廳
主題

ZeroJudge - d273: 11584 - Partitioning by Palindromes 解題心得

Not In My Back Yard | 2021-08-13 00:00:09 | 巴幣 120 | 人氣 429

題目連結:


題目大意:
輸入第一列給定一正整數,代表有多少筆測試資料,每筆佔一列。每列給定一個只由小寫字母組成的字串(長度為 1 ~ 1000 個字元),試問該字串最少可以切成幾個子字串使得每個子字串皆為迴文?



範例輸入:
3
racecar
fastcar
aaadbccb


範例輸出:
1
7
3


解題思維:
令給定的字串為 s 且其長度為 n。

先將 s 的每個可能之子字串 s[i] ~ s[j] 是否是迴文建表為一個二維陣列 P[i][j] 以供查詢。建表方式除了直觀的窮舉 (i, j) 然後去檢查的 O(n ^ 3) 作法以外,可以在 O(n ^ 2) 之內做到:
以兩個變數 L = R = i 作為開端然後重複以下步驟直到 L 或 R 其中一者超出 s 的索引值範圍或是 s[L] ≠ s[R] 為止:
P[i][j] = 真(True);
L 減 1 而 R 加 1。

這樣便可以窮舉出所有以 s[i] 為中心、長度為奇數且可能為迴文的子字串們。而當我們遇到 s[L] ≠ s[R] 時,就代表著 s[L - 1] ~ s[R + 1] 、 s[L - 2] ~ s[R + 2] 等等就不可能是迴文也就不必繼續窮舉下去了。

而我們也可以同理求出所有以 s[i] 和 s[i + 1] 作為中心的子字串們,藉由 L = i 、 R = i + 1 然後仿照以上步驟往左右擴張即可。



而有了迴文表可以查詢後,我們便可以利用動態規劃(Dynamic Programming)求出所求:定義一個一維陣列 D,其中 D[0] = 0(方便用的初始條件)、D[i + 1] 為 s[0] ~ s[i] (i ≧ 0)最少可以被切成幾個迴文子字串。
而我們可以看到 D[i + 1] 之值即為
min(D[j]) + 1
其中 j ≦ i 且 s[j] ~ s[i] 為一迴文(當 j = i 時,必為迴文所以至少會有一項)。

因此我們從 i = 0 掃到 i = n - 1,然後對每個 i 值窮舉 j 值去判斷並更新 D[i + 1] 即可。

總體時間複雜度為建表的 O(n ^ 2) + DP 的 O(n ^ 2) = O(n ^ 2)。而所求即為 D[n]。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作