三亚房地产网站制作,网站基础服务,html怎么做网站设计,芜湖市建设投资有限公司网站目录 一、问题描述
二、解题思路
三、代码
四、复杂度分析 一、问题描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后#xff0c;短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s…目录 一、问题描述
二、解题思路
三、代码
四、复杂度分析 一、问题描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s如果它是 回文串 返回 true 否则返回 false 。
二、解题思路
✅ 题目要求
判断一个字符串是否是回文串忽略大小写并且忽略非字母数字字符。 ✅ 解题关键点 忽略大小写 → 所以我们要用 tolower() 把字符都转成小写。 只保留字母和数字 → 所以要用 isalnum() 判断是否是有效字符字母或数字。 对称比较字符 → 使用双指针从两端往中间走判断字符是否一致。 ✅ 举例说明
示例A man, a plan, a canal: Panama 过滤掉空格、标点只保留字母数字 → AmanaplanacanalPanama 转为小写 → amanaplanacanalpanama 判断是否正着读和反着读一致是回文→ ✅ ✅ 双指针解法步骤模拟过程
假设原字符串是 ab#cB!a 过滤后变成 abcba left 0指向 a right 6指向 a → 相等继续 left 1指向 b right 5指向 B → 转成小写后也等继续 left 2指向 c right 4指向 c → 相等继续
最终 left right说明每一对字符都匹配 → ✅ 是回文
三、代码
class Solution {
public:bool isPalindrome(string s) {int left 0; // 左指针指向字符串开头int right s.size() - 1; // 右指针指向字符串末尾while (left right) {// 如果左指针不是字母或数字向右移动while (left right !isalnum(s[left])) left;// 如果右指针不是字母或数字向左移动while (left right !isalnum(s[right])) --right;// 对比当前字符都转成小写不相等则不是回文if (tolower(s[left]) ! tolower(s[right])) {return false;}// 移动两个指针继续比较left;--right;}return true; // 成功通过所有对比说明是回文}
};四、复杂度分析
项目复杂度说明⏱ 时间复杂度O(n)每个字符最多遍历一次 空间复杂度O(1)使用双指针不额外开辟空间不存储新字符串
