注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(71)-回文子字符串的数目[算法]  

2018-02-23 07:46:27|  分类: 默认分类 |  标签: |举报 |字号 订阅

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

例如,字符串"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代码:


程序员面试题精选100题(71)-朋友圈[算法] - 何海涛 - 微软、Google等面试题

 

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

 

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

 

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

 

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

 

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


程序员面试题精选100题(71)-朋友圈[算法] - 何海涛 - 微软、Google等面试题

  

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


本文转载自微信公众号青云算法扫描下面的二维码,关注“青云算法”微信公众号,学习更多高频算法面试题的解法。

程序员面试题精选100题(65)-每天的温度[算法] - 何海涛 - 微软、Google等面试题

  评论这张
 
阅读(586)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018