力扣(LeetCode)647

lemanli 发布于2019-08-19 11:34 / 2071人阅读

摘要：示例输入输出解释三个回文子串示例输入输出说明个回文子串注意输入的字符串长度不会超过。解答这一题可以用穷举法，检查是否为回文字串但是应该会超时。设置表示是否是回文字串，若是为，否则为。

题目地址：
https://leetcode-cn.com/probl...
题目描述：
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".
示例 2:

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
注意:

输入的字符串长度不会超过1000。

解答：
这一题可以用穷举法，检查s[i...j]是否为回文字串但是应该会超时。
不过我们可以这么想，如果现在知道了s[i...j]是回文字串，那么如果
s[i-1] == s[j+1]，那么s[i-1...j+1]也一定是回文字串。这样就联想到了
动态规划。
设置dp[i] [j]表示s[i...j]是否是回文字串，若是为true，否则为false。
那么对任意的dp[i] [j] = dp[i+1] [j-1]&&s[i]==s[j]。一旦为true就把
结果+1。
不过需要注意的是要使用上述的递推公式，需要先求出所有长度为1和为2的回文字串，这个比较
简单，就不赘述了。
java ac代码：

class Solution {
    public int countSubstrings(String s) {
        //dp[i][j]表示s[i...j]是否为回文字串。
        boolean[][] dp = new boolean[s.length()][s.length()];
        int ans = 0;
        for(int i = 0;i < dp.length;i++)
        {
            dp[i][i] = true;
            ans++;
        }
        for(int i = 1;i < dp.length;i++)
        if(s.charAt(i-1) == s.charAt(i))
        {
            dp[i-1][i] = true;
            ans++;
        }
        for(int k = 2;k < s.length();k++)
            for(int i = k;i < s.length();i++)
                if(s.charAt(i-k) == s.charAt(i)&&dp[i-k+1][i-1])
                {
                    dp[i-k][i] = true;
                    ans++;
                }
        return ans;
    }
}

云服务器 GPU云服务器力扣 LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77458.html

[LeetCode] 647. Palindromic Substrings

Problem 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 c...

邹立鹏 2019-08-19 11:11 评论0 收藏0
力扣(LeetCode)310

摘要：图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度，若入度为就是叶子节点。题目地址：https://leetcode-cn.com/probl...题目描述：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小...

amuqiao 2019-08-16 16:13 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0
力扣(LeetCode)452

摘要：对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。解答这是一道区间覆盖问题，不太好说清楚，利用模板即可。题目地址：https://leetcode-cn.com/probl...题目描述：在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方...

fanux 2019-08-16 15:20 评论0 收藏0