验证回文串

逃离我推掉我的手 2023-06-08 14:59 45阅读 0赞

**验证回文串**

> **题目描述:**
> 
> 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
> 
> 说明：本题中，我们将空字符串定义为有效的回文串。
> 
> 示例 1:
> 
> 输入: "A man, a plan, a canal: Panama"  
> 输出: true  
> 示例 2:
> 
> 输入: "race a car"  
> 输出: false
> 
> 来源：力扣（LeetCode）  
> **[OJ链接][OJ]  
> 分析:**
> 
> 最简单的思路是遍历这个字符串, 将其中所有的字母和数字按顺序存到另一个新串中, 然后判断这个新串是否是回文串, 这就好办了, 同时从前从后遍历, 一个字符一个字符的判断就行了.但这种放到新串中的方式效率稍低一点, 我们也可以直接遍历传进来的字符串, 不过代码稍麻烦一点
> 
> 因为不区分大小写 ,所以有一个不值得注意的坑, 'A'+32='a', '0'+32='p', 所以不能只判断+32是否相等, 还要区分数字和字母
> 
> 两种都实现一下, 上代码

方法一: 定义一个新串

class Solution {
    public:
    	bool isPalindrome(string s) {
    		string t;
    		char ch1, ch2;
    		for (auto i : s) {
    			if (i >= 'a'&&i <= 'z' || i >= 'A'&&i <= 'Z' || i >= '0'&&i <= '9') { 
    				t.push_back(i);
    			}
    		}
    		for (int i = 0, j = t.size() - 1; i < j; ++i, --j) {
    			ch1 = t[i];
    			ch2 = t[j];
    			if ( ch1 >= '0'&& ch1 <= '9' && (ch2 < '0' || ch2 > '9')) {
    				return false;
    			}
    			if (ch2 >= '0'&&ch2 <= '9' && (ch1 < '0' || ch1 > '9')) {
    				return false;
    			}
    			if (ch1 != ch2 && ch1 + 32 != ch2 && ch2 + 32 != ch1) {
    				return false;
    			}
    		}
    		return true;
    	}
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70][]

方法二 : 直接遍历

class Solution {
    public:
        bool isPalindrome(string s) {
    	int size = s.size();
    	char ch1, ch2;
    	for (int i = 0, j = size - 1; i < j; ++i, --j) {
    	    ch1 = s[i];
    	    while ((ch1 < 'a' || ch1 > 'z') && (ch1 < 'A' || ch1 > 'Z') && (ch1 < '0' || ch1 > '9')) {
    		++i;
    		if (i == size) return true;
    		ch1 = s[i];
    	    }
    	    if (i > j) return true;
    	    ch2= s[j];
    	    while ((ch2 < 'a' || ch2 > 'z') && (ch2 < 'A' || ch2 > 'Z') && (ch2 < '0' || ch2 > '9')) {
    		--j;
    		if (i > j) return false;
    		ch2 = s[j];
    	    }
    	    if (ch1 >= '0'&&ch1 <= '9' && (ch2 < '0' || ch2 > '9')) {
    		return false;
    	    }
    	    if (ch2 >= '0'&&ch2 <= '9' && (ch1 < '0' || ch1 > '9')) {
    		return false;
    	    }
    	    if (ch1 != ch2 && ch1 + 32 != ch2 && ch2 + 32 != ch1) {
    		return false;
    	    }
    	}
    	return true;
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1][]

[OJ]: https://leetcode-cn.com/problems/valid-palindrome
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70]: /images/20230531/ce9fb6aab5e14a63a39036d688ad03e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1]: /images/20230531/b482c4c8d9ff49ce810b5e22a645d996.png