統計字元串中不同迴文子序列的個數
統計字元串中不同迴文子序列的個數
作者:Grey
原文地址: 統計字元串中不同迴文子序列的個數
問題描述
給定一個字元串str,當然可以生成很多子序列,返回有多少個子序列是迴文子序列,空序列不算迴文,比如,str = 「aba」
迴文子序列有
{a}:0位置上的a
{a}:2位置上的a
{a,a}
{b}
{a,b,a}
所以返回5。
暴力解法
枚舉每個子序列,然後判斷子序列是否是迴文,程式碼如下
public static int ways1(String str) {
if (str == null || str.length() == 0) {
return 0;
}
char[] s = str.toCharArray();
char[] path = new char[s.length];
return process(str.toCharArray(), 0, path, 0);
}
// 枚舉每個位置要或者不要情況下,得到迴文子序列的個數是多少
public static int process(char[] s, int si, char[] path, int pi) {
if (si == s.length) {
return isP(path, pi) ? 1 : 0;
}
int ans = process(s, si + 1, path, pi);
path[pi] = s[si];
ans += process(s, si + 1, path, pi + 1);
return ans;
}
// 判斷path串中0...pi-1是不是迴文
public static boolean isP(char[] path, int pi) {
if (pi == 0) {
return false;
}
int L = 0;
int R = pi - 1;
while (L < R) {
if (path[L++] != path[R--]) {
return false;
}
}
return true;
}
動態規劃解
定義二維數組dp
,數組長度假設為n
int[][] dp = new int[n][n]
dp[i][j]
的含義是:字元串[i...j]
區間內可以得到的最多迴文子序列個數,所以,dp[0][n-1]
的值就是我們需要求的最終答案。
根據dp
數組的含義,我們可以得到,二維矩陣dp
中的對角線上的值都是1, 對角線上面的位置也可以很容易得出,見如下注釋
// 對角線上的值都是1
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 對角線上面的位置,即dp[i][i+1]上的值
// 如果str[i] == str[i+1],比如:aa,有三個迴文子序列,分別是{a},{a},{aa}
// 如果str[i] != str[i+1],比如:ab,有兩個迴文子序列,分別是 {a},{b}
for (int i = 0; i < n - 1; i++) {
dp[i][i+1] = str[i] == str[i+1] ? 3 : 2;
}
接下來考慮普遍位置dp[i][j]
,可以有如下幾種情況:
情況一,i
位置的字元棄而不用,那麼dp[i][j] = dp[i+1][j]
;
情況二,j
位置的字元棄而不用,那麼dp[i][j] = dp[i][j-1]
;
基於情況一和情況二,
dp[i][j] = dp[i+1][j] + dp[i][j-1]
這個時候,其實是算重了一部分,算重的部分是dp[i+1][j-1]
,所以
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
如果str[i] == str[j]
,則存在情況三,情況三中,str[i]
和str[j]
可都保留,與區間[i+1...j-1]
形成迴文串,str[i]
也可以單獨和str[j]
形成一個迴文串。所以,情況三
// dp[i][j]分成兩部分
// 其中:
// 第一部分:dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] 表示i位置和j位置棄而不用的情況下,得到的答案數
// 第二部分:dp[i + 1][j - 1] + 1 表示在情況三下,同時使用str[i]和str[j]位置得到的答案數
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + dp[i + 1][j - 1] + 1
動態規劃解法的完整程式碼
public static int ways2(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = s.toCharArray();
int n = str.length;
int[][] dp = new int[n][n];
// 對角線都是1
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int i = 0; i < n - 1; i++) {
dp[i][i + 1] = str[i] == str[i + 1] ? 3 : 2;
}
for (int i = n - 3; i >= 0; i--) {
for (int j = i + 2; j < n; j++) {
// 減去dp[i+1][j-1]是因為算重複了
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
if (str[i] == str[j]) {
// dp[i][j]分成兩部分
// 其中:
// 第一部分:dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] 表示i位置和j位置棄而不用的情況下,得到的答案數
// 第二部分:dp[i + 1][j - 1] + 1 表示在情況三下,同時使用str[i]和str[j]位置得到的答案數
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + dp[i + 1][j - 1] + 1;
}
}
}
return dp[0][n - 1];
}