上海企乐网站制作公司,商标设计网站图,京津冀协同发展的基础,天津网站设计 河西一、题目描述 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后#xff0c;短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s#xff0c;如果它是 回文串 #xff0c;返回 true #xff1b…一、题目描述 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s如果它是 回文串 返回 true 否则返回 false 。
二、测试用例
示例 1
输入: s A man, a plan, a canal: Panama
输出true
解释amanaplanacanalpanama 是回文串。示例 2
输入s race a car
输出false
解释raceacar 不是回文串。示例 3
输入s
输出true
解释在移除非字母数字字符之后s 是一个空字符串 。
由于空字符串正着反着读都一样所以是回文串。提示
1 s.length 2 * 105
s 仅由可打印的 ASCII 字符组成三、解题思路
基本思路 头指针尾指针一直判断是否相等直到两指针相遇或者字符不相等停止具体思路 预处理定义 trim(string s) 函数功能是删除非字母或数字的字符并且字符转小写。使用双指针实现i 指针用于保存字符j 指针用于遍历遇到要保持的就赋值给 i 指针最后删除多余字符。双指针遍历先使用 trim 函数处理字符串因为回文串中心对称所以我们从两端开始一直判断是否相同。定义头指针 i 和尾指针 j 初始化为 0 和 n-1 。判断两指针所指字符是否相同相同就继续判断下一个i 和 j-- 。不同则表示不是回文串返回 false 。直到两指针相遇都相同则表示是回文串返回 true 。
四、参考代码
时间复杂度 O ( n ) \Omicron(n) O(n) 空间复杂度 O ( 1 ) \Omicron(1) O(1)
class Solution {
public:void trim(string s) {int n s.length();int i 0, j 0;while (j n) {s[j] tolower(s[j]);if (isalnum(s[j])) {s[i] s[j];} else {j;}}s.erase(i, n - i);}bool isPalindrome(string s) {trim(s);int n s.length();for (int i 0, j n - 1; i j; i, j--) {if (s[i] ! s[j]) {return false;}}return true;}
};
