下面的代碼給了我最長的回文子序列長度。如何修改代碼以獲得最長的回文子字串長度？
public static int lp(String str, int i, int j, int ans) {
if (i == str.length() || j <= 0)
return ans;
if (i > j)
return ans;
if (i == j)
return ans 1;
if (str.charAt(i) == str.charAt(j)) {
int a = lp(str, i 1, j, ans);
int b = lp(str, i, j - 1, ans);
int c = lp(str, i 1, j - 1, ans 2);
ans = Math.max(Math.max(a, b), c);
return ans;
} else {
int a = lp(str, i 1, j, ans);
int b = lp(str, i, j - 1, ans);
ans = Math.max(a, b);
return ans;
}
}
這是一個示例呼叫：
String s = "sbsncjss";
// longest subsequence length is 5 and longest substring length is 3
System.out.println("Ans is " lp(s, 0, s.length() - 1, 0));
uj5u.com熱心網友回復：
如何修改代碼以獲得最長的回文子串長度
然后，您需要排除跳過字符的情況。當您的代碼將要跳過一個字符時，搜索可以繼續，但ans重置為 0。
所以：
public static int lp(String str, int i, int j, int ans) {
if (i == str.length() || j <= 0)
return ans;
if (i > j)
return ans;
if (i == j)
return ans 1;
if (str.charAt(i) == str.charAt(j)) {
int a = lp(str, i 1, j, 0); // <-- reset!
int b = lp(str, i, j - 1, 0); // <-- reset!
int c = lp(str, i 1, j - 1, ans 2);
ans = Math.max(Math.max(a, b), c);
return ans;
} else {
int a = lp(str, i 1, j, 0); // <-- reset!
int b = lp(str, i, j - 1, 0); // <-- reset!
ans = Math.max(a, b);
return ans;
}
}
請注意，盡管這可行，但有更有效的演算法可以找到最長的回文子串。但是它們與您提出的最長回文子序列演算法完全不同，因此只需進行一些更改就不是問題了。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/497500.html
上一篇：FirebaseOTP在除錯apk上作業正常，但不能發布apk
下一篇：使用遞回時追加時串列為空