首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

回文子字符串的数目

问题:给你一个字符串,请输出该字符串里有多少个回文子字符串。如果两个子字符串的起始位置或者结束位置不同,那么即使它们的内容一样也是不同的子字符串。

例如,字符串"abc"有3个回文子字符串,分别为"a"、"b"和"c";"aaa"有6个回文子字符串,分别为"a"、"a"、"a"、"aa"、"aa"和"aaa"。

分析:

这是LeetCode的第647题。

解法一:动态规划

我们分析以字符串中第i个字符结尾的子字符串中回文的数目。首先,任意一个字符本身都是一个长度为1的回文子字符串。

其次,如果第i个字符和它前面的第i-1个字符相同。那么,它们组成一个长度为2的回文子字符串。例如:字符串"abba"中,两个相邻的"b"组成一个长度为2的回文"bb"。

另外,如果以第i-1个字符为结尾的子字符串中有一个长度为m的回文子字符串,并且第i个字符和该回文前面一个字符(下标为i-m-1)相同,那么以第i个字符结尾的子字符串中有一个长度为m+2的回文。例如字符串"abba"中,下标为3的字符"a"(下标从0开始计数)前面有一个长度为2的回文"bb",由于"bb"的前面的字符也是"a",因此它们共同组成一个长度为4的回文"abba"。

基于这个思路,我们可以写出如下的Java代码:

在上述代码中,链表prevLengths是以第i-1个字符为结尾的所有回文子字符串的长度。由于需要这么一个链表,因此该解法的空间复杂度是O(n)。另外,由于该解法需要两个嵌套的循环,因此时间复杂度是O(n^2)。

解法二:从回文的特点入手

如果我们找到一个长度为m的回文子字符串,我们分别向该回文的两端延伸一个字符,并判断回文前后的字符是否相同。如果相同,我们就找到了一个长度为m+2的回文。例如,在字符串"abcba"中,我们从中间的"c"出发向两端延伸一个字符,由于"c"前后都是"b",因此我们找到了一个长度为3的回文"bcb"。接着我们再向两端延伸一个字符,由于"bcb"的前后都是"a",所以我们有找到一个长度为5 的回文"abcba"。

值得注意的是,回文的长度可以是奇数,也可以是偶数。长度为奇数的回文,其对称中心只有一个字符;而长度为偶数的回文,其对称中心有两个字符。

基于这个思路,我们可以写出如下代码:

上述解法仍然需要两个嵌套的循环,因此时间复杂度还是O(n^2)。但该解法只用到了若干变量,其空间复杂度是O(1)。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180206G06CQ700?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

相关快讯

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券