給定一個二進制字串 S，找出長度為 5 的回文子序列的數量。長度為 5 的回文子序列是陣列 a < b < c < d < e 的 5 個遞增索引的串列，使得 S[a ]S[b]S[c]S[d]S[e] 形成回文。如果兩個回文子序列的索引串列不同，則認為它們是不同的。
我的想法：
我想出了一個遞回如下：
palin(s) = palin(s[1:]) palin(s[:-1]) -palin(s[1:-1])
當 s[0] !=s[-1] 時會出現上述情況。我們可以類似地處理其他情況。但這并不僅僅處理長度為 5 的回文。它將回傳回文子序列的總數。我不確定這是否可以擴展以找到解決方案。有什么想法嗎？
uj5u.com熱心網友回復：
考慮下一個（線性復雜性）方法：
長度為 5 的回文由任意中心數字組成，左邊有一對0..0, 0..1, 1..0, 1..1數字，左邊有一對對稱數字0..0, 1..0, 0..1, 1..1。
因此，您可以從左到右遍歷字串，存盤每個索引左側的每種可能對的數量，反向執行相同操作。i那么以索引為中心的回文數為
P[i] = (Num of 00 left to i) * (Num of 00 right to i)
(Num of 01 left to i) * (Num of 10 right to i)
(Num of 10 left to i) * (Num of 01 right to i)
(Num of 11 left to i) * (Num of 11 right to i)
并且回文的總數是P[i]超i=2..Len-2范圍的總和
如何獲得留給 i 的對數？只需計算 0 和 1，并使用這些計數：
if S[i-1] == 0:
(Num of 01 left to i) = (Num of 01 left to i-1)
(Num of 11 left to i) = (Num of 11 left to i-1)
(Num of 10 left to i) = (Num of 10 left to i-1) (Count_1)
(Num of 00 left to i) = (Num of 00 left to i-1) (Count_0)
Count_0 = 1
else: # 1 forms new 0-1 pairs for all 0's at the left
# and new 1-1 pairs for all 1's at the left
(Num of 01 left to i) = (Num of 01 left to i-1) (Count_0)
(Num of 11 left to i) = (Num of 11 left to i-1) (Count_1)
(Num of 00 left to i) = (Num of 00 left to i-1)
(Num of 10 left to i) = (Num of 10 left to i-1)
Count_1 = 1
要檢查的 Python 代碼（啞函式檢查所有可能的組合以批準結果）
import itertools
def dumb(s):
n = len(s)
res = 0
# produces all indices combinations
for comb in itertools.combinations(range(n), 5):
if s[comb[0]]==s[comb[4]] and s[comb[1]]==s[comb[3]]:
res = 1
return res
def countPal5(s):
n = len(s)
pairs = [[0, 0, 0, 0] for _ in range(n)]
cnts = [0,0]
for i in range(1, n-2):
if s[i-1] == "0":
if i >= 2:
pairs[i-1][0]=pairs[i-2][0] cnts[0]
pairs[i-1][1]=pairs[i-2][1]
pairs[i-1][2]=pairs[i-2][2] cnts[1]
pairs[i-1][3]=pairs[i-2][3]
cnts[0] = 1
else:
if i >= 2:
pairs[i-1][0]=pairs[i-2][0]
pairs[i-1][1]=pairs[i-2][1] cnts[0]
pairs[i-1][2]=pairs[i-2][2]
pairs[i-1][3]=pairs[i-2][3] cnts[1]
cnts[1] = 1
#print(pairs)
cnts = [0,0]
res = 0
for i in range(n-2, 1, -1):
if s[i 1] == "0":
if i < n-2:
pairs[i 1][0]=pairs[i 2][0] cnts[0]
pairs[i 1][1]=pairs[i 2][1]
pairs[i 1][2]=pairs[i 2][2] cnts[1]
pairs[i 1][3]=pairs[i 2][3]
cnts[0] = 1
else:
if i < n-2:
pairs[i 1][0]=pairs[i 2][0]
pairs[i 1][1]=pairs[i 2][1] cnts[0]
pairs[i 1][2]=pairs[i 2][2]
pairs[i 1][3]=pairs[i 2][3] cnts[1]
cnts[1] = 1
res = pairs[i 1][0]*pairs[i-1][0] pairs[i 1][1]*pairs[i-1][2] pairs[i 1][2]*pairs[i-1][1] pairs[i 1][3]*pairs[i-1][3]
return res
print(pairs)
print(countPal5("0110101001"))
print(dumb("0110101001"))
>>68
>>68
uj5u.com熱心網友回復：
- 假設您有一個函式
count(pattern, l,r)回傳 substring 中模式的出現次數string[l:r]。 - 對于每個索引，將其視為回文子串的中心。左邊有 2 個元素，右邊有 2 個元素。現在，這 2 個元素只能有 4 個不同的值（從 0 到 3）。
- 對于 index ，其中心為元素
i的回文字串的數量為，其中is 在范圍內，并回傳 integer 的二進制字串表示形式。i-thsum(count(binary(x), 0,i) count(binary(x).reverse, i, len(string)))x[0,3]binary(x)x
這種方法需要O(n * 4 * complexity of count function)時間。
如何構建count功能？通過預處理/記憶，您可以輕松地及時獲取模式出現的數量O(1)。提示：只有 4 個模式要跟蹤，每個模式只需要 2 個計數。簡單的計數和操作就可以完成作業。
uj5u.com熱心網友回復：
只有 8 個長度為 5 的回文字串。生成所有長度為 5 的子序列，并在存盤的表中查找它們。
import itertools
palindromes= ("00000", "00100", "01010", "01110", "10001", "10101", "11011", "11111")
count= 0
for s in itertools.combinations("01100111", 5):
if "".join(s) in palindromes:
count = 1
print(count)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505877.html
標籤：算法
上一篇：使用隨機樞軸C實作就地快速排序