# A typical way to solve *palindrome* problems

• Here's a typical way to solve palindrome problems using DP.
For palindrome sequence, there are two sub problems(palindrome with even length and palindrome with odd length).
How to solve palindrome problems according to these two categories makes me crazy for a long time.

Then I come up with a typical solution after reading several solutions for each palindrome problems. Hope it helps!

1. We first define a 2D array.
2. Initialize dp[i][i] according to each problems.
3. Initialize dp[i][i+1].
4. To find dp[i][j] iteratively, we start from gap = 2 (which means the length of current subsequence is 3).

For example, for sequence "aaa",
gap = 2, i = 0, then j = i + gap = 2.
s.charAt(i) == s.charAt(j),
then, dp[i][j] = dp[i + 1][j - 1] + 2 = dp[1][1] + 2 = 3.

Thus, the relation function can be reached by

``````for (int gap = 2; gap < s.length(); gap++) {
for (int i = 0; i < s.length() - gap; i++) {
int j = i + gap;
if (s.charAt(i) == s.charAt(j)) {
/ ***** /
} else {
/ ***** /
}
}
}
``````

Longest Palindromic Subsequence

``````    public int longestPalindromeSubseq(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[][] f = new int[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
f[i][i] = 1;
}
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) == s.charAt(i + 1)) {
f[i][i + 1] = 2;
} else {
f[i][i + 1] = 1;
}
}
for (int gap = 2; gap < s.length(); gap++) {
for (int i = 0; i < s.length() - gap; i++) {
int j = i + gap;
if (s.charAt(i) == s.charAt(j)) {
f[i][j] = f[i + 1][j - 1] + 2;
} else {
f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
}
}
}
return f[0][s.length() - 1];
}
``````

Number of Palindrome Substring
Given "aaa"
return 6
("a" "a" "a" "aa" "aa" "aaa") There are 6 Palindromic substrings.

``````	public static int countPalindromSubstring(String s) {
if(s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int count = 0;
boolean[][] f = new boolean[n][n];
for(int i = 0; i < n; i++) {
f[i][i] = true;
count++;
}
for(int i = 0; i < n - 1; i++) {
if(s.charAt(i) == s.charAt(i + 1)) {
f[i][i + 1] = true;
count++;
}
}
for(int gap = 2; gap < n; gap++) {
for(int i = 0; i < n - gap; i++) {
int j = i + gap;
if(s.charAt(i) == s.charAt(j)) {
if(f[i + 1][j - 1]) {
f[i][j] = true;
count++;
}
}
}
}
return count;
}
``````

• nice solution!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.