647.Palindromic-Substrings

647. Palindromic Substrings

题目地址

题目描述

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.

代码

Approach #1

class Solution {
int count = 0;
public int countSubstrings(String s) {
if (s == null || s.length() == 0) return 0;
​
for (int i = 0; i < s.length(); i++) {
extendPalindrome(s, i, i);
extendPalindrome(s, i, i + 1);
}
​
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++;
}
}
}

Approach #1 Expand Around Center

Time O(N^2) Space O(1)
class Solution {
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;
}
}

Approach #2 Manacher's Algorithm

Time O(N) Space O(N)
class Solution {
public int countSubstrings(String S) {
char[] A = new char[2 * S.length() + 3];
A[0] = '@';
A[1] = '#';
A[A.length - 1] = '$';
int t = 2;
for (char c: S.toCharArray()) {
A[t++] = c;
A[t++] = '#';
}
​
int[] Z = new int[A.length];
int center = 0, right = 0;
for (int i = 1; i < Z.length - 1; i++) {
if (i < right) {
Z[i] = Math.min(right - i, Z[2 * center - i]);
}
while (A[i + Z[i] + 1] == A[i - Z[i] - 1]) {
Z[i]++;
}
if (i + Z[i] > right) {
center = i;
right = i + Z[i];
}
}
int ans = 0;
for (int v: Z) {
ans += (v + 1) / 2;
}
​
return ans;
}
}