文档章节

计算字符串中回文子串的个数 Palindromic Substrings

叶枫啦啦
 叶枫啦啦
发布于 2018/01/13 10:00
字数 391
阅读 417
收藏 0

问题:

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

  1. The input string length won't exceed 1000.

解决:

①  计算字符串中回文子串的个数,使用动态规划解决:

d[i][j]表示从i到j的字符串为是否回文,真则为(1),否则为假(0),

那么d[i][j]为真的前提是:头尾两个字符串相同并且去掉头尾以后的字串也是回文(即d[i+1][j-1]为真),这里面要注意特殊情况,即:去掉头尾以后为空串,所以如果j-i<3,并且头尾相等,也是回文的。

class Solution { //22ms
    public int countSubstrings(String s) {
        int len = s.length();
        int res = 0;
        boolean[][] dp = new boolean[len][len];
        for (int i = len - 1;i >= 0;i --){
            for (int j = i;j < len;j ++){
                dp[i][j] = ((s.charAt(i) == s.charAt(j) && ((j - i < 3) || dp[i + 1][j - 1])));
                if (dp[i][j]){
                    res ++;
                }
            }
        }
        return res;
    }
}

② 从中间向两边递归判断回文字符串。

class Solution { //12ms
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;
        int len = s.length();
        int res = 0;
        for (int i = 0;i < len;i ++){
            res += dfs(s,i,i);
            res += dfs(s,i,i + 1);
        }
        return res;
    }
    public int dfs(String s,int left,int right){
        int res = 0;
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left --;
            right ++;
            res ++;
        }
        return res;
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 19
博文 583
码字总数 400448
作品 0
海淀
私信 提问
加载中

评论(0)

【DP、双指针】647. Palindromic Substrings

题目描述: Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as differ......

牛奶芝麻
2019/06/06
0
0
647. Palindromic Substrings

问题 求一个字符有多少个回文子串 Input: "abc" Output: 3 Input: "aaa" Output: 6 思路和代码(1)——朴素做法 用dp的基本思想“子问题求解”,但是因为没有重叠子问题,没必要用dp数组或者...

PilgrimHui
2018/10/08
0
0
LeetCode 647. Palindromic Substrings (回文子字符串)

原题 Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different su......

dby_freedom
2018/12/19
0
0
【Leetcode】647. Palindromic Substrings

Description Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as diffe......

xiagnming
2018/07/30
0
0
【DP、双指针】5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Example 2: 解题思路: 找一个字符串的最长回文子串,......

牛奶芝麻
2019/06/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

0228 我的潘多拉

我的潘多拉 从一个故事说起。<br />从前,有个Java程序员非常喜欢写程序,喜欢研究源码,读英文文档。但是它在一家小公司里工作,公司的技术栈很陈旧。<br /> <br />单个系统代码中含有很多的...

李福春carter
今天
18
0
OSChina 周六乱弹 —— 屁会不会传染病毒

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《ハレハレヤ(朗朗晴天)》- 猫瑾 手机党少年们想听歌,请使劲儿戳(这里) @空格...

小小编辑
今天
63
1
两个值得注意的问题

对成员变量的操作只能放在方法中,方法可以对成员变量和方法体中自己定义的局部 变量进行操作.在定义类的成员变量时可以同时赋予初值,如 class A { int a=12; float b=12.56f; } 但是不可以这...

咔啡
今天
27
0
第三章 分布式服务框架的选择

1.大项目工程且多人维护的弊端 (1)项目团队协同成本高,业务响应越来越慢 (2)应用复杂度已超出人的认知负载(向杂乱的电线一样) (3)错误难于隔离(一个模块出错,整个系统挂掉) (4...

zxx901221
今天
68
0
eclipse 上传jar到远程仓库

使用maven的项目中,有时需要把本地的项目打成jar包上传到mevan仓库。 操作如下: 前提:pom文件中配置好远程库的地址,否则会报错 一、将maven 中的settings文件配置好用户名和密码,如下:...

文文1
昨天
63
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部