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

微软、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代码:

public int countSubstrings(String s) {
    int count = s.length() > 0 ? 1 : 0;
    List<Integer> prevLengths = new LinkedList<>();
    prevLengths.add(1);
    for (int i = 1; i < s.length(); ++i) {
        List<Integer> curLengths = new LinkedList<>();
        curLengths.add(1);
        if (s.charAt(i) == s.charAt(i - 1)) {
            curLengths.add(2);
        }

        for (int prevLength : prevLengths) {
            if (i - prevLength - 1 >= 0
                && s.charAt(i) == s.charAt(i - prevLength - 1)) {
                curLengths.add(prevLength + 2);
            }
        }

        count += curLengths.size();
        prevLengths = curLengths;
    }

    return count;
}

 

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

 

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

 

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

 

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

 

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

public int countSubstrings(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }

    int count = 0;
    for (int i = 0; i < s.length(); ++i) {
        count += countPalindrome(s, i, i);
        count += countPalindrome(s, i, i + 1);
    }

    return count;
}

private int countPalindrome(String s, int start, int end) {
    int count = 0;
    while (start >= 0 && end < s.length()
           && s.charAt(start) == s.charAt(end)) {
        count++;
        start--;
        end++;
    }

    return count;
}

  

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


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

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

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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