Related palindrome questions (Java)
Palindrome
- aba
- abba
- Shanghai tap water comes from the sea
- The plane flew into the sky
Valid Palindrome
Several common functions of Java character classes
- isLetter(c)
- isDigit(c)
- toLowerCase(c)
- toUpperCase(c)
//Validate if the character is the letter or digit
public boolean isValid(char c) {
return Character.isLetter(c) || Character.isDigit(c);
}
//Validate if the two data equal
public boolean isEquals(String s, int left, int right) {
return s.toLowerCase().charAt(left) == s.toLowerCase().charAt(right);
}
public boolean isPalindrome(String s) {
if (s == null) {
return true;
}
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !isValid(s.charAt(left))) {
left++;
}
while (left < right && !isValid(s.charAt(right))) {
right--;
}
if (left < right && !isEquals(s, left, right)) {
return false;
}
left++;
right--;
}
return true;
}Longest Subsequence
Subsequence: discontinuous characters
Order of magnitude: o(
), each character can be selected or not
Example: abcd
a b c d / ab ac ad bc bd cd / abc abd acd bcd / abcd
Train of thought dynamic planning
For any string
If the first and last characters are the same, then the longest subsequence of the string = the longest subsequence of the string with the first and last characters removed + the first and last characters
If the first and last characters are different, the longest subsequence = the larger: remove the longest subsequence of the first string and the longest subsequence of the last string
dp[i][j] = dp [i + 1][j - 1] + 2 if (str[i] == str[j])
dp[i][j] = max(dp [i + 1][j], dp [i][j - 1]) if (str[i] != str[j])
public int longestPalindromeSubseq(String s) {
int length = s.length();
if (length == 0)
return 0;
int[][] dp = new int[length][length];
for (int i = length - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < length; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][length - 1];
}Recursive method
public class Solution {
int[][] f = null;
char[] s = null;
int res = 0;
private void Compute(int i, int j) {
if (f[i][j] != -1) {
return;
}
if (i == j) {
f[i][j] = 1;
return;
}
if (i + 1 == j) {
if (s[i] == s[j]) {
f[i][j] = 2;
}
else {
f[i][j] = 1;
}
return;
}
Compute(i + 1, j);
Compute(i, j - 1);
Compute(i + 1, j - 1);
f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
if (s[i] == s[j]) {
f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
}
}
public int longestPalindromeSubseq(String ss) {
s = ss.toCharArray();
int n = s.length;
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int i, j;
f = new int[n][n];
for (i = 0; i < n; ++i) {
for (j = i; j < n; ++j) {
f[i][j] = -1;
}
}
Compute(0, n - 1);
for (i = 0; i < n; ++i) {
for (j = i; j < n; ++j) {
res = Math.max(res, f[i][j]);
}
}
return res;
}
}Non recursive method
public class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int[][] f = new int[n][n];
int i, j, len;
for (i = 0; i < n; ++i) {
f[i][i] = 1;
}
for (i = 0; i < n-1; ++i) {
if (s.charAt(i) == s.charAt(i+1)) {
f[i][i+1] = 2;
}
else {
f[i][i+1] = 1;
}
}
for (len = 3; len <= n; ++len) {
for (i = 0; i <= n-len; ++i) {
j = i + len - 1;
f[i][j] = f[i][j-1];
if (f[i+1][j] > f[i][j]) {
f[i][j] = f[i+1][j];
}
if (s.charAt(i) == s.charAt(j) && f[i+1][j-1] + 2 > f[i][j]) {
f[i][j] = f[i+1][j-1] + 2;
}
}
}
int res = 0;
for (i = 0; i < n; ++i) {
for (j = i; j < n; ++j) {
if (f[i][j] > res) {
res = f[i][j];
}
}
}
return res;
}
}
Longest Palindrome Substring
Substring: consecutive characters
Order of magnitude: o(
), there are 1 + 2 ++ N non empty substrings, i.e. (n + 1) * n / 2
Example: abcd
a b c d / ab bc cd / abc bcd / abcd
Train of thought 1 opposite double pointer O(n^3)
Starting point O(n) --------- (detect whether the intermediate substring is a palindrome string) O(n) ----------end point O(n)
a b c a a b c a
^^ = = > ^ ^ = = > unequal end
l r l r
a b b a a b b a a b b a
^^ = = > ^ ^ = = > ^ ^ = = > end of encounter
l r l r r l
public String longestPalindrome(String s) {
if (s == null) {
retrun null;
}
for (int length = s.length(); length >=1; length --) {
for (int start = 0; start <= s.length() - length ; start++) {
if (isPalindrome(s, start, start + length - 1)) {
return s.substring(start, start + length);
}
}
}
return "";
}
public boolean isPalindrome(String s, int left, int right) {
while (left < right && s.charAt(left) == s.charAt(right)) {
left++:
right--;
}
return left >= right;
}Train of thought 2 enumerate center point O(n^2)
t|a{bcb}a|c
Avoid duplicate detection of bcb
tabcbac => t|a|b|b|a|c t|a|b|b|a|c t|a|b|b|a|c --> L+1 ~ R-1
< -- > -- > the length is an odd number, and there are n central points of the palindrome string
t|a|b|b|a|c => t|a|b|y|b|a|c t|a|b|y|b|a|c t|a|b|y|b|a|c t|a|b|y|b|a|c --> L+1 ~ R-1
< -- > -- > the length is even, and there are n-1 palindrome string centers
public String longestPalindrome(String s) {
if (s == null) {
return null;
}
String longest = "";
for (int i = 0; i < s.length(); i++) {
// odd number
String oddPalindrome = getPalindromeFrom(s, i, i);
if (longest.length() < oddPalindrom.length()){
longest = oddPalindrome;
}
//even number
String evenPalindrome = getPalindromeFrom(s, i, i+1);
if (longest.length() < evenPalindrome.length()){
longest = evenPalindrome;
}
}
return longest;
}
public String getPalindromeFrom(String s, int left, int right){
while (left >=0 && right < s.length()) {
if (s.charAt(left) != s.charAt(right)){
break;
}
left--:
right++;
}
return s.substring(left + 1, right);
}Idea 3 dynamic programming
Dynamic planning: the status of this stage is the result of the status of the previous stage and the decision of the previous stage
State transition equation:
Known status of stage K
, decision in stage K
If 
Then
, i.e
Set [Row(r), Column(c)] =
[0,0], [1,1], [2,2], [3,3], [4,4], [5,5], [6,6] = > a single character must be a palindrome string [0,0], [1,1], [2,2], [3,3] = > a single character must be a palindrome string
[0,1], [1,2], [2,3], [3,4], [4,5], [5,6] = > there is no palindrome string in the two character combinations [0,1], [1,2], [2,3] = > there is palindrome string in the two character combinations
Reverse the order of the circulating lines, judge the Boolean values of the remaining empty cells, point to the smaller value of the True value range at the starting position of the cutting string, and the length of the palindrome string is the number of values of the True value range(
)
| x | a | b | c | b | a | t | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| x T | xa F | xab F | xabc F | xabcb F | xabcba F | xabcbat F | 0 |
| null | a T | ab F | abc F | abcb F | abcba T | abcbat F | 1 |
| null | null | b T | bc F | bcb T | bcba F | bcbat F | 2 |
| null | null | null | c T | cb F | cba F | cbat F | 3 |
| null | null | null | null | b T | ba F | bat F | 4 |
| null | null | null | null | null | a T | at F | 5 |
| null | null | null | null | null | null | t T | 6 |
| a | b | b | a | |
|---|---|---|---|---|
| 0 | 1 | 2 | 3 | |
| a T | ab F | abb F | abba T | 0 |
| null | b T | bb T | bba F | 1 |
| null | null | b T | ba F | 2 |
| null | null | null | a T | 3 |
public String longestPalindrome(String s) {
if (s == null || s.equals("")) {
return "";
}
int n = s.length();
boolean[][] isPalindrome = new boolean[n][n];
int longest = 1, start = 0;
//Set single palindrome string status
for (int i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
for (int i = 0; i< n - 1; i++) {
isPalindrome[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
if (isPalindrome[i][i + 1]) {
start = i;
longest = 2;
}
}
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 2; j < n; j++){
isPalindrome[i][j] = isPalindrome[i + 1][j - 1] &&
s.charAt(i) == s.charAt(j);
if (isPalindrome[i][j] && j - i + 1 > longest) {
start = i;
longest = j - i + 1;
}
}
}
return s.substring(start, start + longest);
}