旅游网站设计源码,wordpress 的论坛模板下载,做刀模网站,做外贸比较好用的网站链接验证回文串题序号125类型字符串解题方法双指针法难度简单
题目 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后#xff0c;短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s#xf…链接验证回文串题序号125类型字符串解题方法双指针法难度简单
题目 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 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 * 105s 仅由可打印的 ASCII 字符组成 解题
双指针法
核心点忽略大小写、忽略非字母数字字符时间复杂度O(n);空间复杂度O(1);c 判断字符串是否只包含字母和数字函数isalnum()c 字符串比较函数tolower()c实现算法
class Solution {
public:bool isPalindrome(string s) {int left 0, right s.size() - 1;while (left right) {// 跳过非字母和数字字符if (!isalnum(s[left])) {left;continue;}if (!isalnum(s[right])) {right--;continue;}// 比较字符忽略大小写if (tolower(s[left]) ! tolower(s[right])) {return false;}// 移动指针left;right--;}return true;}
};演示以示例2为例
完整 c demo
#include iostream
#include string
#include cctype // 用于isalnum()
using namespace std;class Solution {
public:bool isPalindrome(string s) {int left 0, right s.size() - 1;while (left right) {// 跳过非字母和数字字符if (!isalnum(s[left])) {left;continue;}if (!isalnum(s[right])) {right--;continue;} // 比较字符忽略大小写if (tolower(s[left]) ! tolower(s[right])) {return false;}// 移动指针left;right--;}return true;}
};int main() {Solution sol;// 测试1string test1 A man, a plan, a canal: Panama;cout Test 1: test1 endl;cout Is palindrome? (sol.isPalindrome(test1) ? Yes : No) endl;// 测试2string test2 race a car;cout Test 2: test2 endl;cout test2 size: test2.size() endl;cout Is palindrome? (sol.isPalindrome(test2) ? Yes : No) endl;// 测试3string test3 ;cout Test 3: test3 endl;cout Is palindrome? (sol.isPalindrome(test3) ? Yes : No) endl;// 测试4string test4 ab_a;cout Test 4: test4 endl;cout Is palindrome? (sol.isPalindrome(test4) ? Yes : No) endl;return 0;
}
