字符串(马拉车)_leetcode.647.回文子串

发表于 | 分类于 ， | 热度: ℃
字数统计: 2.7k | 阅读时长 ≈ 10

🌸题目

🍁给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

1
2
3
4
5
6
7
8
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：

输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

输入的字符串长度不会超过 1000 。

🍁分析

计算有多少个回文子串的最朴素方法就是枚举出所有的回文子串，而枚举出所有的回文字串又有两种思路，分别是：

  • 枚举出所有的子串，然后再判断这些子串是否是文;
  • 枚举每一个可能的回文中心，然后两个指针分别向左右两边拓展，当两个
    指针指向的元素相同的时候就拓展，则停止拓展。

假设字符串的长度为n。我们可以看出前者会用O(n2 )的时间枚举出所有的子串
s[li..ri],然后再用O(r;- li + 1)的时间检测当前的子串是否是文,整个
算法的时间复杂度是O(n3)。后者枚举文中心的是0(n)的,对于每个文
中心拓展的次数也是0(n)的，所以时间复杂度是O(n2)。所以我们选择第二种
方法来枚举所有的回文子串。

🍁解法一：暴力优化（动态规划）

🍂 直接暴力枚举这里就不贴了，这里贴暴力的优化利用动态规划。但是也同样是中心扩散思想。

暴力法主要浪费在判断回文串上，不能有效利用同中心的回文串的状态，简单来说就是此时我们假设前面的子串s[j,i]是回文串，那么，子串s[j-1,i+1]也有可能是回文串，不难想出当且仅当子串s[j,i]是回文串且s[j-1]=s[i+1]时，子串s[j-1,i+1]也是回文串，于是我们可以通过数组保存子串是否是回文串，然后通过递推上一次的状态，得到下一次的状态，属于动态规划的解法，令dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串，状态转移如下：

当 s[i] == s[j] && (j - i < 2 || dp[i + 1] [j - 1])时，dp[i] [j]=true，否则为false

  • 当只有一个字符时，比如a自然是一个回文串。
  • 当有两个字符时，如果是相等的，比如aa，也是一个回文串。
  • 当有三个及以上字符时，比如ababa 这个字符记作串1,把两边的a去掉,
    也就是bab记作串2，可以看出只要串2是一个回文串,那么左右各多了一
    个a的串1必定也是文串。所以当s[i]==s[j] 时,自然要看dp[i+1] [j- 1]是不是一个回文串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int countSubstrings2(String s) {
	boolean[][] dp = new boolean[s.length()][s.length()];
	int res = 0;
	
	for(int j = 0; j < s.length(); j++) {
		for(int i = 0; i <= j; i++) {
			if(s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
				dp[i][j] = true;
				res++;
			}
		}
	}
	return res;
}

🍁解法二： 中心拓展法

🍂 比如对一个字符串ababa ,选择最中间的a作为中心点往两边扩散,第- -次扩 散发现left指向的是b，right 指向的也是b，所以回文串，继续扩散,同理ababa也回文串。
这个是确定了一一个中心后的寻找的路径，然后我们只要寻找到所有的中心点，问题就解决了。

中心点-共有多少个呢?看起来像是和字符串长度相等，但你会发现,如果是这样，上面的例子永远也搜不到 abab ，想象一下单个字符的哪个中心点扩展可以得到这个子串?似乎不可能。所以中心点不能只有单个字符构成，还要包括两个字符，比如上面这个子串abab ，就可以有中心点ba扩展一次得到，所以最终的中心2 * 1en- 1个，分别是len个单字符和len - 1个双字符。

如果上面看不太懂的话，还可以看看下面几个问题:

  • 为什么有2* len- 1个中心点?
    • aba 5个中心点，分别是a、b、a、ab、ba
    • abba有7个中心点，分别是a、b、b、a、ab、bb、ba
  • 什么是中心点?
    • 中心点即left指针和right指针初始化指向的地方，可能是一个也可能是两个
  • 为什么不可能是三个或者更多?
    • 因为3个可以由1个扩展一次得到，4个可以由两个扩展一次得到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int countSubstrings(String s) {
	//中心扩展
	int res = 0;
	for(int center = 0; center < 2 * s.length() - 1; center++) {
		// 首先是left，有一个很明显的2倍关系的存在，其次是right，可能和left指向同一个（偶数时），也可能往后移动一个（奇数）
		int left = center / 2;
		int right = left + center % 2;
		
		while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
			res++;
			left--;
			right++;
		}
	}
	return res;
}

这个解法也同样适用于leetcode 5 最长回文子串，按上述代码，稍作修改，即可得到，第五题的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String longestPalindrome(String s) {
        // ababa 求最长公共子串
        int len = s.length();
        String result = "";

        for (int i = 0; i < len * 2 - 1; i++) {
            int left = i / 2;
            int right = left + i % 2;
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                String tmp = s.substring(left, right + 1);
                if (tmp.length() > result.length()) {
                    result = tmp;
                }
                left--;
                right++;
            }
        }
        return result;
    }
}

🍁解法三：Manacher 算法

🍂 Manacher算法是在线性时间内求解最长文子串的算法。在本题中，我们要求解
回文串的个数，为什么也能使用Manacher算法呢?这里我们就需要理解一下
Manacher的基本原理。

Manacher算法也会面临方法一」中的奇数长度和偶数长度的问题， 它的处理方
式是在所有的相邻字符中间插入#,比如abaa会被处理成#a#b#a#a#，
这样可以保证所有找到的回文串都是奇数长度的，以任意一个字符为文中心,
既可以包含原来的奇数长度的情况，也可以包含原来偶数长度的情况。假设原字
符串为s,经过这个处理之后的字符串为s。

我们用f(i)来示以s的第i位为回文中心，可以拓展出的最大回文半径,那么
f(i)- 1就是以i为中心的最大文串长度(想-想为什么)

Manacher算法依旧需要枚举s的每一个位置并先假设它回文中心,但是它会利用经计算出来的状态来更新f(i),而不向「中心拓展| -样盲目地拓展。具体地说，假设我们已经计算好了[1,i- 1]区间内所有点的f (即我们知道[1,i- 1]这些点作为文中心时候的最大半径)，那么我们也就知道了[1,i一1]拓展出的回文达到最大半径时的回文右端点。例如i = 4的时候f(i)= 5,说明以第4个元素为回文中心，最大能拓展到的回文半径是5,此时右端为4+5-1= 8。所以当我们知道一 个i对应的f(i)的时候,我们就可以很容易.得到它的右端点为i+ f(i)- 1。

Manacher算法如何通过已经计算出的状态来更新f(i)呢? Manacher算法要求
我们维护「当前最大的回文的右端点$$r_m$$」以及这个回文右端点对应的回文中心
$$i_m$$.我们需要顺序遍历s,假设当前遍历的下标为i。我们知道在求解f(i)之前
我们应当已经得到了从[1,i- 1] 所有的f,并且当前已经有了一个最大回文右端
点$$r_m$$以及它对应的回文中心$$i_m$$.

  • 初始化 f(i)

    • 如果i < rm,说明i被包含在当前最大回文子串内，假设j是i关于
      这个最大回文的回文中心im的对称位置(即j+i=2 x im) ,我们
      可以得到f(i)至少等于min{f(j),rm-i+1}.这里将f(j)和
      rm-i+ 1取小，先要保证这个文串在当前最大文串内。(思
      考:为什么f(j)有可能大于rm-i+1? )
    • 如果i > rm,那就先初始化f(i)= 1。

  • 中心拓展

    • 做完初始化之后，我们可以保证此时的 s[i + f(i) - 1] = s[i - f(i) + 1]，要继续拓展这个区间，我们就要继续判断 s[i + f(i)] 和 s[i - f(i)] 是否相等，如果相等将 f(i)自增；这样循环直到 s[i + f(i)]不等于 s[i - f(i)]，以此类推。我们可以看出循环每次结束时都能保证 s[i + f(i) - 1] = s[i - f(i) + 1]，而循环继续（即可拓展的条件）一定是 s[i + f(i)] = s[i - f(i)]。 这个时候我们需要注意的是不能让下标越界，有一个很简单的办法，就是在开头加一个 $，并在结尾加一个 !!，这样开头和结尾的两个字符一定不相等，循环就可以在这里终止。

这样我们可以得到 s所有点为中心的最大回文半径，也就能够得到 S 中所有可能的回文中心的的最大回文半径，把它们累加就可以得到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int countSubstrings3(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]
        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;
}

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！

-------------本文结束感谢您的阅读-------------
云澈 wechat
扫一扫，用手机访问哦
坚持原创技术分享，您的支持将鼓励我继续创作！
0%