給定一個 String s，回傳長度為 5 的回文子序列的數量。
測驗用例 1：
input : "abcdba"
Output : 2
"abcba" and "abdba"
測驗用例 2：
input : "aabccba"
Output : 4
"abcba" , "abcba" , "abcba" , "abcba"
最大字串長度：700
我的 TLE 方法：O(2^n)
https://www.online-java.com/5YegWkAVad
任何輸入都受到高度贊賞......
uj5u.com熱心網友回復：
- 每當 2 個字符匹配時，我們只需要找出這 2 個字符之間可能有多少長度為 3 的回文。
例如：
a bcbc a
^ ^
|_ _ _ |
在上面的示例中，您可以找到 2 個長度3為bcb和的回文cbc。因此，我們可以制作長度5為abcba或的回文序列acbca。因此，答案是2。
如果我們第一次不快取結果，那么計算每個子字串有多少長度為 3 的回文數可能會很耗時。因此，快取這些結果并將它們重用于由其他 2 個字符匹配生成的查詢。(
a.k.a dynamic programming)這樣，解決方案變為二次
O(n^2)時間，其中n是字串的長度。
片段：
private static long solve(String s){
long ans = 0;
int len = s.length();
long[][] dp = new long[len][len];
/* compute how many palindromes of length 3 are possible for every 2 characters match */
for(int i = len - 2;i >= 0; --i){
for(int j = i 2; j < len; j){
dp[i][j] = dp[i][j-1] (dp[i 1][j] == dp[i 1][j-1] ? 0 : dp[i 1][j] - dp[i 1][j - 1]);
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = j - i - 1;
}
}
}
/* re-use the above data to calculate for palindromes of length 5*/
for(int i = 0; i < len; i){
for(int j = i 4; j < len; j){
if(s.charAt(i) == s.charAt(j)){
ans = dp[i 1][j - 1];
}
}
}
//for(int i=0;i<len; i) System.out.println(Arrays.toString(dp[i]));
return ans;
}
在線演示
更新：
dp[i][j] = dp[i][j-1] (dp[i 1][j] == dp[i 1][j-1] ? 0 : dp[i 1][j] - dp[i 1][j - 1]);
上面這行基本上就是這個意思，
- 對于任何子串，比如說
bcbcb，匹配first 和 lastb，總共 3 個長度的回文串可以加上- 可能的總計數
bcbc。 - 可能的總計數
cbcb。 - 可能的總計數
bcbcb（(j - i - 1)在if條件下）。
- 可能的總計數
dp[i][j]對于手頭的當前子字串。dp[i][j-1]- 添加長度為 3 的先前子字串計數。在此示例中，bcbc.dp[i 1][j], 添加以當前索引結尾的子字串，不包括第一個字符。（這里，cbcb）。dp[i 1][j] == dp[i 1][j-1] ? 0 : dp[i 1][j] - dp[i 1][j - 1]這是為了基本上避免內部子字串的重復計數，并且只有在計數存在差異時才添加它們。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/472648.html