LeetCode C++ 680. Valid Palindrome II【String】简单
发布日期:2021-07-01 02:52:21
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月15日 08时43分59秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
scala list
2019-05-01
svn服务器安装
2019-05-01
spark 笔记1
2019-05-01
shell dirname basename
2019-05-01
未来已至,5G加持下的云游戏将走向何方?
2019-05-01
计算机网络 —— 网络层 1.
2019-05-01
Android 之 ContentProvider 与 ContentResolver
2019-05-01
【接口自动化】
2019-05-01
推荐一位川大零基础转行 Python 的人生勇士
2019-05-01
Python解惑之:True与False
2019-05-01
你要的微信小程序终于来了
2019-05-01
有了这些 Chrome 插件,效率提升10倍(建议收藏)
2019-05-01
Python 开发者都会遇到的错误:UnboundLocalError
2019-05-01
只有1%的程序员搞懂过浮点数陷阱
2019-05-01
一名 Google 工程师的大数据处理经验
2019-05-01
命名难,难于上青天
2019-05-01
没钱没公司,怎么做一款付费产品
2019-05-01
代码整洁之道-编写 Pythonic 代码
2019-05-01
树莓派程序开机自启动
2019-05-01