[LeetCode] 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 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. 

这道题给了我们一个字符串,让我们计算有多少个回文子字符串。博主看到这个题,下意识的想着应该是用DP来做,哼哼哧哧写了半天,修修补补,终于通过了,但是博主写的DP不是最简便的方法,略显复杂,这里就不贴了。还是直接讲解大神们的解法好了。其实这道题也可以用递归来做,而且思路非常的简单粗暴。就是以字符串中的每一个字符都当作回文串中间的位置,然后向两边扩散,每当成功匹配两个左右两个字符,结果res自增1,然后再比较下一对。注意回文字符串有奇数和偶数两种形式,如果是奇数长度,那么i位置就是中间那个字符的位置,所以我们左右两遍都从i开始遍历;如果是偶数长度的,那么i是最中间两个字符的左边那个,右边那个就是i+1,这样就能cover所有的情况啦,而且都是不同的回文子字符串,参见代码如下:

解法一:

class Solution {

public:
    int countSubstrings(string s) {
        if (s.empty()) return 0;
        int n = s.size(), res = 0;
        for (int i = 0; i < n; ++i) {
            helper(s, i, i, res);
            helper(s, i, i + 1, res);
        }
        return res;
    }
    void helper(string s, int i, int j, int& res) {
        while (i >= 0 && j < s.size() && s[i] == s[j]) {
            --i; ++j; ++res;
        }
    }
};

在刚开始的时候博主提到了自己写的DP的方法比较复杂,为什么呢,因为博主的dp[i][j]定义的是范围[i, j]之间的子字符串的个数,这样我们其实还需要一个二维数组来记录子字符串[i, j]是否是回文串,那么我们直接就将dp[i][j]定义成子字符串[i, j]是否是回文串就行了,然后我们i从n-1往0遍历,j从i往n-1遍历,然后我们看s[i]和s[j]是否相等,这时候我们需要留意一下,有了s[i]和s[j]相等这个条件后,i和j的位置关系很重要,如果i和j相等了,那么dp[i][j]肯定是true;如果i和j是相邻的,那么dp[i][j]也是true;如果i和j中间只有一个字符,那么dp[i][j]还是true;如果中间有多余一个字符存在,那么我们需要看dp[i+1][j-1]是否为true,若为true,那么dp[i][j]就是true。赋值dp[i][j]后,如果其为true,结果res自增1,参见代码如下: 

解法二:

class Solution {

public:
    int countSubstrings(string s) {
        int n = s.size(), res = 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);
                if (dp[i][j]) ++res;
            }
        }
        return res;
    }
};

参考资料:

https://discuss.leetcode.com/topic/96819/java-solution-8-lines-extendpalindrome

https://discuss.leetcode.com/topic/96884/very-simple-java-solution-with-detail-explanation

https://discuss.leetcode.com/topic/96821/java-dp-solution-based-on-longest-palindromic-substring

本文转自博客园Grandyang的博客,原文链接:[LeetCode] Palindromic Substrings 回文子字符串

,如需转载请自行联系原博主。

时间: 2024-10-23 05:13:06

[LeetCode] Palindromic Substrings 回文子字符串的相关文章

LeetCode 5 Longest Palindromic Substring(最大回文子字符串)

翻译 给定一个字符串S,找出它的最大回文子字符串. 你可以假定S的最大长度为1000, 并且这里存在唯一一个最大回文子字符串. 原文 Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 暴力搜索,O(n

[LeetCode] Count Binary Substrings 统计二进制子字符串

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the numbe

Java实现查找当前字符串最大回文串代码分享_java

先看代码 public class MaxHuiWen { public static void main(String[] args) { // TODO Auto-generated method stub String s = "abb"; MaxHuiWen(s); } //1.输出回文串 public static void MaxHuiWen(String s){ //存储字符串的长度 int length = s.length(); //存储最长的回文串 String M

微软编程之美——回文字符序列

描述 给定字符串,求它的回文子序列个数.回文子序列反转字符顺序后仍然与原序列相同.例如字符串aba中,回文子序列为"a", "a", "aa", "b", "aba",共5个.内容相同位置不同的子序列算不同的子序列. 限制 时间限制:2000ms 单点时限:1000ms 内存限制:256MB 输入 第一行一个整数T,表示数据组数.之后是T组数据,每组数据为一行字符串. 输出 对于每组数据输出一行,格式为&q

leetcode 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, and there exists one unique longest palindromic substring. 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的.比如"a" , "aaabbaaa" 之前

[LeetCode] Count Different Palindromic Subsequences 计数不同的回文子序列的个数

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7. A subsequence of a string S is obtained by deleting 0 or more characters from S. A sequence is palindromic if it is equal

[LeetCode] Valid Palindrome II 验证回文字符串之二

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome. Example 1: Input: "aba" Output: True Example 2: Input: "abca" Output: True Explanation: You could delete the character 'c'. N

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, and there exists one unique longest palindromic substring. 求字符串的最长回文子串 算法1:暴力解法,枚举所有子串,对每个子串判断是否为回文,复杂度为O(n^3) 算法2:删除暴力解法中有很多重复的判

算法:uva 11404 Palindromic Subsequence(LCS回文串,最小字典序)

题目大意 给一个字符串,输出它的最长回文串,如果有多个结果,输出字典序最小的. 思 路 我们都知道把一个字符串逆序后和原字符串进最长公共子序列,可以计算出它的最长回文串长度. 但是这题不仅要输出回文串,而且还要求是字典序最小的,所以挺难搞的. 设str1是正序字符串, str2是逆序后的字符串 f[i][j].len 表示str1的前i位,str2的前j位,最长公共子串的长度 f[i] [j].str 表示str1的前i位,str2的前j位,最长公共子串的最小字典序的字符串 状态转移和正常的LC