C++实现LeetCode(647.回文子字符串)

这篇文章主要介绍了C++实现LeetCode(647.回文子字符串),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下

C++实现LeetCode(647.回文子字符串),恰卡网带你了解更多相关信息。

[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 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));        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;    }};

到此这篇关于C++实现LeetCode(647.回文子字符串)的文章就介绍到这了,更多相关C++实现回文子字符串内容请搜索趣讯吧以前的文章或继续浏览下面的相关文章希望大家以后多多支持趣讯吧!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,请发送邮件至 55@qq.com 举报,一经查实,本站将立刻删除。转转请注明出处:https://www.szhjjp.com/n/2109.html

(0)
nan
上一篇 2021-07-10
下一篇 2021-07-10

相关推荐

  • 季节性过敏性鼻炎怎么治最有效?

    认识季节性过敏性鼻炎季节性过敏性鼻炎是一种常见的过敏性疾病,多发生在春秋季节。它是由身体对花粉和尘螨等过敏原过度反应引起的。症状包括打喷嚏、鼻塞、流鼻涕、鼻痒等,严重影响患者的生活质量。治疗季节性过敏性鼻炎的方法有很多,下面详细介绍。使用药物治疗药物治疗是缓解季节性过敏性鼻炎症状的主要方法之一。常用的药物包括抗组胺药、鼻类固醇喷雾剂和口服抗过敏药物。抗组胺药可以有效缓解打喷嚏和流鼻涕等症状,但对

    2023-09-27
    0
  • 未央小说叫什么我靠谈恋爱证道飞升-我靠谈恋爱证道飞升未央全文免费阅读

    鸣人没有盖棺定论,只是点到为止,毕竟他们都在寻找答案。 不必纠结与自己的执念到底是什么,名可名也,非常名也,只要知道大概的方向就可以一点点摸索出自己的道。 哪怕同样是为了被爱,有人会整容,有人会讨好他人,有人会四处留情… 每个人都不一样。 答案不再外边,在内心深处。 “多谢你。” 未央在苌葙的指点下用修仙界仍然通用的拱手礼郑重道谢。 她并没有跟任何人说过自己关于道是三观的看法,鸣人却脱口就是“

    网络资讯 2023-05-22
    0
  • ​清道夫鱼为什么不能吃 清道夫有多可怕

    清道夫鱼一般都是生活在比较严重的水域,在食物短缺时有时还会吃垃圾或者是吃腐肉。这导致体内会有许多的有害细菌或者是有害物质,我们如果处理不正确,对个人的健康可能会产生影响。清道夫鱼是什么?清道夫鱼这是一种淡水鱼类,主要是在亚洲热带或者是南美洲。基本上都会有灰黑色的皮肤上面,还可以看到许多的鳞片。最终会凭借着独特的清洁习惯而得到人们的认可。主要会清洁水中的一些垃圾,或者是死亡生物在原生水域或者水族馆,

    2023-11-17
    0
  • 百分爆评热文韩宁薄时予,韩宁薄时予推荐阅读

    小橙几乎要哭出来了:“沐姐,咱别参加这个节目了吧。”韩宁有些茫然:“怎么了吗?”小橙哭道:“自从沐姐你参加这个节目,一直出事,这是上天不想让你继续参加了啊!”小橙是她在一众实习助理里一眼挑中的,图的就是她心地善良。如今小橙这么说,韩宁也知道小橙确实关心她。

    2023-08-30
    0
  • 电竞圈地震!Uzi被曝加盟EDG霸榜热搜 网友心急等官宣 !

    《英雄联盟》LPL赛区传奇选手——Uzi再次重新连接?6月8日消息,今日,《英雄联盟》电竞圈知名人士“Mr_谢帆”透露:“EDG.Uzi 正在聊ing,搓手等结果”。随后,Uzi加盟EDG的消息在网上引起热议,多个话题冲上微博热搜,其中“Uzi EDG”更是霸榜热搜第一。值得一提的是,有网友发现ED

    2023-06-09 热点头条
    0
  • 她是大佬男主的白月光阮嫆凌也小说免费阅读无弹窗大结局-她是大佬男主的白月光(她是大佬男主的白月光)小说全文阅读

    凌也握着手机的手收紧,瞬间怒上心头,冲动的问话几乎脱口而出,“那你怎么……”他话没问出口,但阮嫆知道他想说什么。凌也的绝情,让她彻底认清了男人这种生物,她不再期盼爱情,唯有金钱是最大的安全感。想起凌也酒后无情冷漠的那句,“我宁愿要外面的女人,也不愿碰你。”凌也确实做到了,婚后两年从未碰过她。

    网络资讯 2023-06-13
    0

发表回复

登录后才能评论