问题
- 给定一个字符串 s ,请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
解决
//1、遍历统计(双指针),时间复杂度O(n^3)
class Solution {
public int countSubstrings(String s) {
int low,heigh;
int count=0;
for(int i=0;i<s.length();i++){
low=i;
for(int j=i;j<s.length();j++){
heigh=j;
if(isVaild(s,low,heigh)){
count++;
}
}
}
return count;
}
public boolean isVaild(String s,int l,int r){
while(l<r){
if(s.charAt(l)!=s.charAt(r))
{
return false;
}
l++; //记住判断以后要移位
r--;
}
return true;
}
}
// 2、遍历统计(中心拓展),时间复杂度O(n^2)
class Solution {
public int countSubstrings(String s) {
int n = s.length(), ans = 0;
for (int i = 0; i < 2 * n - 1; ++i) {
int l = i / 2, r = i / 2 + i % 2; //从回文中心开始拓展,分奇偶。一样是遍历所有子串
while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
--l;
++r;
++ans;
}
}
return ans;
}
}
//3、Manacher算法,时间复杂度O(nlogn)
class Solution {
public int countSubstrings(String s) {
//处理字符串
int n = s.length();
StringBuffer t = new StringBuffer("$#");
for (int i = 0; i < n; ++i) {
t.append(s.charAt(i));
t.append('#');
}
n = t.length();
t.append('!');
//创建对应的最大回文半径数组
int[] f = new int[n];
int iMax = 0, rMax = 0, ans = 0; //回文中心,回文半径,子回文数
for (int i = 1; i < n; ++i) { //每个回文中心的回文半径
// 初始化 f[i],要么是1,要么是
f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;
// 中心拓展
while (t.charAt(i + f[i]) == t.charAt(i - f[i])) {
++f[i];
}
// 动态维护 iMax 和 rMax
if (i + f[i] - 1 > rMax) {
iMax = i;
rMax = i + f[i] - 1;
}
// 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
ans += f[i] / 2;
}
return ans;
}
}
//4、Manacher算法修整版
class Solution{
public static char[] manacherString(String str) {
char[] charArr = str.toCharArray();
char[] res = new char[str.length() * 2 + 1];
int index = 0;
for (int i = 0; i != res.length; i++) {
res[i] = (i & 1) == 0 ? '#' : charArr[index++]; //让字符串中的字符于#交替存储
}
return res; //返回处理好的字符数组
}
public static int countSubstrings(String str) {
if (str == null || str.length() == 0) {
return 0;
}
char[] charArr = manacherString(str); //项原始字符串添加虚拟(辅助)字符'#'
int[] pArr = new int[charArr.length]; //用来存储charArr每一位对应的最大回文长度
int C = -1; //回文中心
int R = -1; //最大回文半径
int sum=0;
for (int i = 0; i != charArr.length; i++) { //以数组中每个字符为中心
pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1; //当i被R包主时,pArr的取值
while (i + pArr[i] < charArr.length && i - pArr[i] > -1) { //当前位置+/-最大半径数都在charArr数组长度里
if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) //暴力扩最大半径
pArr[i]++;
else {
break;
}
}
if (i + pArr[i] > R) { //如果i的最大半径大于R
R = i + pArr[i]; //将R扩到当前位置+最大半径
C = i; //C也移到i位置
}
sum+=pArr[i]>>1; //使用位运算更快
}
return sum;
}
}
原创文章,作者:,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/278528.html