LeetCode C++ 680. Valid Palindrome II【String】简单
发布日期:2021-07-01 02:52:21
浏览次数:3
分类:技术文章
本文共 1951 字,大约阅读时间需要 6 分钟。
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: TrueExplanation: You could delete the character 'c'.
Note: The string will only contain lowercase characters a-z
. The maximum length of the string is 50000
.
题意:给定一个非空字符串 s
,最多删除一个字符。判断是否能成为回文字符串。
思路1:暴力算法
枚举不删除和删除一个字符的所有情况,代码如下:
class Solution { public: bool isPalindrome(const string &s) { for (int i = 0, j = s.size() - 1; i <= j; ++i, --j) if (s[i] != s[j]) return false; return true; } bool validPalindrome(string s) { if (s.size() <= 2 || isPalindrome(s)) return true; int n = s.size(); for (int i = 0; i < n; ++i) if (isPalindrome(s.substr(0, i) + s.substr(i + 1))) return true; return false; }};
这种暴力算法,时间复杂度是 O ( n 2 ) O(n^2) O(n2) 。果然,一提交就超出时间限制。
思路2:利用回文串特征
利用回文串的特征:在回文串左边和右边,分别添加字符串 str
和逆转的字符串 rev_str
,结果还是回文串。因此,我们从左右两端向中间开始验证是否是回文串,验证的过程中:
- 如果不存在两个不等的字符,则整个字符串就是回文串,直接返回
false
; - 如果存在两个不等的字符,则判断删除一个字符后的字符串是不是回文串:
- 以
"abdda"
这个串为例,如果left = 'b', right = 'd'
,发现不一致,但是我们有一次删除的机会; - 那么很容易知道,此时
(left + 1, right)
或者(left, right - 1)
这两个子串中只要有任意一个是回文串,则结果就是回文串。 - 如果这两个子串都不是回文串,那么无论删不删除、删除
left = 'b'
还是删除right = 'd'
,结果都不会是回文串。
- 以
C++代码如下:
class Solution { public: bool isPalindrome(const string &s, int b, int e) { for (int i = b, j = e; i <= j; ++i, --j) if (s[i] != s[j]) return false; return true; } bool validPalindrome(string s) { if (s.size() <= 2) return true; for (int left = 0, right = s.size() - 1; left < right; ++left, --right) if (s[left] != s[right]) return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1); return true; }};
算法的复杂度是 O ( n ) O(n) O(n) ,效率如下:
执行用时:80 ms, 在所有 C++ 提交中击败了92.48% 的用户内存消耗:19.2 MB, 在所有 C++ 提交中击败了70.96% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108810966 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月20日 00时56分50秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
linux epoll简介
2019-05-02
python装饰器学习总结
2019-05-02
我在Facebook学到的10个经验
2019-05-02
c语言知识点补遗
2019-05-02
python开发总结五
2019-05-02
EL、JSTL、servlet
2019-05-02
2 QCreator调试并查看源码
2019-05-02
4 Qt 之 pro 配置多个子工程/子模块
2019-05-02
12 Qt 之 QToolBox、QLCDNumber
2019-05-02
32 Qt 之绘图之绘制一个漂亮的西瓜
2019-05-02
33 Qt 之绘图之绘制卡通蚂蚁
2019-05-02
35 Qt 之绘制闪烁文本
2019-05-02
QT知识点总结(一)
2019-05-02
Unix环境变量--文件操作
2019-05-02
Unix环境变量--进程管理
2019-05-02
Unix环境变量--线程基础
2019-05-02
Unix环境变量--缓冲区
2019-05-02
Unix环境变量--POSIX异步I/O
2019-05-02
tinyhttpd源码学习1
2019-05-02
Plus One
2019-05-02