https://leetcode.com/problems/palindromic-substrings
https://discuss.leetcode.com/topic/96869/java-o-n-2-time-o-1-space-solution-with-comments
https://discuss.leetcode.com/topic/96884/very-simple-java-solution-with-detail-explanation
https://leetcode.com/problems/palindromic-substrings/discuss/105688/Very-Simple-Java-Solution-with-Detail-Explanation
此算法保证了在扩展时，没有重复的i和j，需要证明下
X. DP
https://leetcode.com/problems/palindromic-substrings/discuss/144443/Logical-Thinking-with-Java-Code
采用区间DP记录被访问过的index
public int countSubstrings(String s) { int n = s.length(); char[] cs = s.toCharArray(); boolean[][] dp = new boolean[n][n]; int ans = 0; for (int i = 0; i < n; ++i){ for (int j = i; j >= 0; --j){ if (i == j || (dp[i - 1][j + 1] && cs[i] == cs[j]) || (cs[i] == cs[j] && i - j == 1)){ dp[i][j] = true; ans ++; } } } return ans; }
X.Brute Force
之所以暴力，是因为即使在某种状态下的substring已经不是palindrome，在它基础上还会分别向外扩展去判断其它的substring是否为palindrome，这一部分可以省去，比如
abacba 判断 ac是否为palindrome，如果ac不是palindrome，那么由此衍生出来的substring a. bacb b. abacba 这两种情况是可以避免的，也是接下来算法优化的核心思路。
public int countSubstrings(String s) { char[] cs = s.toCharArray(); int n = s.length(); int start = 0; int cnt = 0; while (start < n){ for (int i = start; i < n; ++i){ if (isPalidrome(cs, start, i)){ cnt++; } } start++; } return cnt; } public boolean isPalidrome(char[] cs, int i, int j){ while (i < j){ if (cs[i] != cs[j]) return false; i++; j--; } return true; }
http://www.geeksforgeeks.org/count-palindrome-sub-strings-string/
Given a string, the task is to count all palindrome substring in a given string. Length of palindrome substring is greater then or equal to 2.
http://www.geeksforgeeks.org/find-number-distinct-palindromic-sub-strings-given-string/
http://www.geeksforgeeks.org/find-number-distinct-palindromic-sub-strings-given-string/
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
- The input string length won't exceed 1000.
https://discuss.leetcode.com/topic/96869/java-o-n-2-time-o-1-space-solution-with-comments
https://discuss.leetcode.com/topic/96884/very-simple-java-solution-with-detail-explanation
https://leetcode.com/problems/palindromic-substrings/discuss/105688/Very-Simple-Java-Solution-with-Detail-Explanation
此算法保证了在扩展时，没有重复的i和j，需要证明下
public int countSubstrings(String s) {
int sum = 0;
// Loop across different middle points.
for (int i = 0; i < s.length(); i++) {
// Find all odd length palindrome with i as middle point.
sum += findPalindromic(s, i, i);
// Find all even length palindrome with i and i+1 as middle point.
sum += findPalindromic(s, i, i + 1);
}
return sum;
}
// Expend from the current mid point to all of its low and high positions.
private int findPalindromic(String s, int left, int right) {
int count = 0;
// Increase count if the substring is a validate palindrome.
while (left >= 0 && right < s.length() && s.charAt(left--) == s.charAt(right++))
count++;
return count;
} int count = 0;
public int countSubstrings(String s) {
if (s == null || s.length() == 0) return 0;
for (int i = 0; i < s.length(); i++) { // i is the mid point
extendPalindrome(s, i, i); // odd length;
extendPalindrome(s, i, i + 1); // even length
}
return count;
}
private void extendPalindrome(String s, int left, int right) {
while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
count++; left--; right++;
}
}
Let
N be the length of the string. The middle of the palindrome could be in one of 2N - 1 positions: either at letter or between two letters.
For each center, let's count all the palindromes that have this center. Notice that if
[a, b] is a palindromic interval (meaning S[a], S[a+1], ..., S[b] is a palindrome), then [a+1, b-1] is one too.
Algorithm
For each possible palindrome center, let's expand our candidate palindrome on the interval
[left, right] as long as we can. The condition for expanding is left >= 0 and right < N and S[left] == S[right]. That means we want to count a new palindrome S[left], S[left+1], ..., S[right].
public int countSubstrings(String S) {
int N = S.length(), ans = 0;
for (int center = 0; center <= 2 * N - 1; ++center) {
int left = center / 2;
int right = left + center % 2;
while (left >= 0 && right < N && S.charAt(left) == S.charAt(right)) {
ans++;
left--;
right++;
}
}
return ans;
}
https://leetcode.com/problems/palindromic-substrings/discuss/144443/Logical-Thinking-with-Java-Code
state[i][j] is true if substring s[i, j] is palindromic
Aim State
decide all possible state[i][j] and count the element that is true
State Transition
state[i][j] is true if s[i] == s[j] and state[i+1][j-1] is true
state[i][j] is true if s[i] == s[j]
state[i][j] is true
https://leetcode.com/problems/palindromic-substrings/discuss/105707/Java-DP-solution-based-on-longest-palindromic-substringAim State
decide all possible state[i][j] and count the element that is true
State Transition
state[i][j] is true if s[i] == s[j] and state[i+1][j-1] is true
(j - i >= 2)state[i][j] is true if s[i] == s[j]
(j - i == 1)state[i][j] is true
(j - i == 0)
This solution is almost same as the DP solution for longest palindromic substring, instead of storing the longest, just get the count of palindromic substrings.
public int countSubstrings(String s) {
int n = s.length();
int res = 0;
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
if(dp[i][j]) ++res;
}
}
return res;
}采用区间DP记录被访问过的index
public int countSubstrings(String s) { int n = s.length(); char[] cs = s.toCharArray(); boolean[][] dp = new boolean[n][n]; int ans = 0; for (int i = 0; i < n; ++i){ for (int j = i; j >= 0; --j){ if (i == j || (dp[i - 1][j + 1] && cs[i] == cs[j]) || (cs[i] == cs[j] && i - j == 1)){ dp[i][j] = true; ans ++; } } } return ans; }
X.Brute Force
之所以暴力，是因为即使在某种状态下的substring已经不是palindrome，在它基础上还会分别向外扩展去判断其它的substring是否为palindrome，这一部分可以省去，比如
abacba 判断 ac是否为palindrome，如果ac不是palindrome，那么由此衍生出来的substring a. bacb b. abacba 这两种情况是可以避免的，也是接下来算法优化的核心思路。
public int countSubstrings(String s) { char[] cs = s.toCharArray(); int n = s.length(); int start = 0; int cnt = 0; while (start < n){ for (int i = start; i < n; ++i){ if (isPalidrome(cs, start, i)){ cnt++; } } start++; } return cnt; } public boolean isPalidrome(char[] cs, int i, int j){ while (i < j){ if (cs[i] != cs[j]) return false; i++; j--; } return true; }
http://www.geeksforgeeks.org/count-palindrome-sub-strings-string/
Given a string, the task is to count all palindrome substring in a given string. Length of palindrome substring is greater then or equal to 2.
The above problem can be recursively defined.
Initial Values : i = 0, j = n-1;
Given string 'str'
CountPS(i, j)
// If length of string is 2 then we
// check both character are same or not
If (j == i+1)
return str[i] == str[j]
Else If str[i..j] is PALINDROME
// increment count by 1 and check for
// rest palindromic substring (i, j-1), (i+1, j)
// remove common palindrome substring (i+1, j-1)
return countPS(i+1, j) + countPS(i, j-1) + 1 -
countPS(i+1, j-1);
Else // if NOT PALINDROME
// We check for rest palindromic substrings (i, j-1)
// and (i+1, j)
// remove common palindrome substring (i+1 , j-1)
return countPS(i+1, j) + countPS(i, j-1) -
countPS(i+1 , j-1);
int CountPS(char str[], int n){ // creat empty 2-D matrix that counts all palindrome // substring. dp[i][j] stores counts of palindromic // substrings in st[i..j] int dp[n][n]; memset(dp, 0, sizeof(dp)); // P[i][j] = true if substring str[i..j] is palindrome, // else false bool P[n][n]; memset(P, false , sizeof(P)); // palindrome of single lenght for (int i= 0; i< n; i++) P[i][i] = true; // palindrome of length 2 for (int i=0; i<n-1; i++) { if (str[i] == str[i+1]) { P[i][i+1] = true; dp[i][i+1] = 1 ; } } // Palindromes of length more then 2. This loop is similar // to Matrix Chain Multiplication. We start with a gap of // length 2 and fill DP table in a way that gap between // starting and ending indexes increases one by one by // outer loop. for (int gap=2 ; gap<n; gap++) { // Pick starting point for current gap for (int i=0; i<n-gap; i++) { // Set ending point int j = gap + i; // If current string is palindrome if (str[i] == str[j] && P[i+1][j-1] ) P[i][j] = true; // Add current palindrome substring ( + 1) // and rest palinrome substring (dp[i][j-1] + dp[i+1][j]) // remove common palinrome substrings (- dp[i+1][j-1]) if (P[i][j] == true) dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1 - dp[i+1][j-1]; else dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]; } } // return total palindromic substrings return dp[0][n-1];}http://www.geeksforgeeks.org/find-number-distinct-palindromic-sub-strings-given-string/
Given a string of lowercase ASCII characters, find all distinct continuous palindromic sub-strings of it.
void palindromeSubStrs(string s){ map<string, int> m; int n = s.size(); // table for storing results (2 rows for odd- // and even-length palindromes int R[2][n+1]; // Find all sub-string palindromes from the given input // string insert 'guards' to iterate easily over s s = "@" + s + "#"; for (int j = 0; j <= 1; j++) { int rp = 0; // length of 'palindrome radius' R[j][0] = 0; int i = 1; while (i <= n) { // Attempt to expand palindrome centered at i while (s[i - rp - 1] == s[i + j + rp]) rp++; // Incrementing the length of palindromic // radius as and when we find vaid palindrome // Assigning the found palindromic length to odd/even // length array R[j][i] = rp; int k = 1; while ((R[j][i - k] != rp - k) && (k < rp)) { R[j][i + k] = min(R[j][i - k],rp - k); k++; } rp = max(rp - k,0); i += k; } } // remove 'guards' s = s.substr(1, n); // Put all obtained palindromes in a hash map to // find only distinct palindromess m[string(1, s[0])]=1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= 1; j++) for (int rp = R[j][i]; rp > 0; rp--) m[s.substr(i - rp - 1, 2 * rp + j)]=1; m[string(1, s[i])]=1; } //printing all distinct palindromes from hash map cout << "Below are " << m.size()-1 << " palindrome sub-strings"; map<string, int>::iterator ii; for (ii = m.begin(); ii!=m.end(); ++ii) cout << (*ii).first << endl;}http://www.geeksforgeeks.org/find-number-distinct-palindromic-sub-strings-given-string/
Given a string of lowercase ASCII characters, find all distinct continuous palindromic sub-strings of it.
Step 1: Finding all palindromes using modified Manacher’s algorithm:
Considering each character as a pivot, expand on both sides to find the length of both even and odd length palindromes centered at the pivot character under consideration and store the length in the 2 arrays (odd & even).
Time complexity for this step is O(n^2)
Considering each character as a pivot, expand on both sides to find the length of both even and odd length palindromes centered at the pivot character under consideration and store the length in the 2 arrays (odd & even).
Time complexity for this step is O(n^2)
Step 2: Inserting all the found palindromes in a HashMap:
Insert all the palindromes found from the previous step into a HashMap. Also insert all the individual characters from the string into the HashMap (to generate distinct single letter palindromic sub-strings).
Time complexity of this step is O(n^3) assuming that the hash insert search takes O(1) time. Note that there can be at most O(n^2) palindrome sub-strings of a string. In below C++ code ordered hashmap is used where the time complexity of insert and search is O(Logn). In C++, ordered hashmap is implemented using Red Black Tree.
Insert all the palindromes found from the previous step into a HashMap. Also insert all the individual characters from the string into the HashMap (to generate distinct single letter palindromic sub-strings).
Time complexity of this step is O(n^3) assuming that the hash insert search takes O(1) time. Note that there can be at most O(n^2) palindrome sub-strings of a string. In below C++ code ordered hashmap is used where the time complexity of insert and search is O(Logn). In C++, ordered hashmap is implemented using Red Black Tree.
Step 3: Printing the distinct palindromes and number of such distinct palindromes:
The last step is to print all values stored in the HashMap (only distinct elements will be hashed due to the property of HashMap). The size of the map gives the number of distinct palindromic continuous sub-strings.
The last step is to print all values stored in the HashMap (only distinct elements will be hashed due to the property of HashMap). The size of the map gives the number of distinct palindromic continuous sub-strings.
void palindromeSubStrs(string s){ map<string, int> m; int n = s.size(); // table for storing results (2 rows for odd- // and even-length palindromes int R[2][n+1]; // Find all sub-string palindromes from the given input // string insert 'guards' to iterate easily over s s = "@" + s + "#"; for (int j = 0; j <= 1; j++) { int rp = 0; // length of 'palindrome radius' R[j][0] = 0; int i = 1; while (i <= n) { // Attempt to expand palindrome centered at i while (s[i - rp - 1] == s[i + j + rp]) rp++; // Incrementing the length of palindromic // radius as and when we find vaid palindrome // Assigning the found palindromic length to odd/even // length array R[j][i] = rp; int k = 1; while ((R[j][i - k] != rp - k) && (k < rp)) { R[j][i + k] = min(R[j][i - k],rp - k); k++; } rp = max(rp - k,0); i += k; } } // remove 'guards' s = s.substr(1, n); // Put all obtained palindromes in a hash map to // find only distinct palindromess m[string(1, s[0])]=1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= 1; j++) for (int rp = R[j][i]; rp > 0; rp--) m[s.substr(i - rp - 1, 2 * rp + j)]=1; m[string(1, s[i])]=1; } //printing all distinct palindromes from hash map cout << "Below are " << m.size()-1 << " palindrome sub-strings"; map<string, int>::iterator ii; for (ii = m.begin(); ii!=m.end(); ++ii) cout << (*ii).first << endl;}