[Day 30] LeetCode - 125 Valid Palindrome

本篇同步发布於Blog:[解题] LeetCode - 125 Valid Palindrome

平台：

LeetCode

题号：

125 - Valid Palindrome

题目连结：

https://leetcode.com/problems/valid-palindrome/

题目说明：

给1个字串s，求s是否为s的palindrome(回文)，这题的Palindrome的定义是字串的英文字母和数字是左右对称，且英文大小写不分，如果是其他字元则略过不比对。

比如范例输入s = "A man, a plan, a canal: Panama"，它扣掉空白、逗号、分号，全转成小写的话，会是"amanaplanacanalpanama"，会是左右对称的回文。

特殊案例是 s = ",!"，全都只有标点符号，这也是回文。

解题方法：

　建立2个索引值i和j，分别从字串s的左边和右边扫描，找到第1个英文字母或数字则停下，确认是否符合回文定义的比对规则，如果不相同，则并不是回文。当i >= j，代表已经都比对完，则属於回文。

而判断是否相同字母或数字，可以用字元的ASCII范围检查，并回传自定义的索引值，比如'A'和'a'回传0、'0'回传26(与前面英文字母不同)。

难度为Easy

程序码 (C++ 与 C#)：

#include <iostream>
using namespace std;

class Solution {
private: 
    int getAlphanumericCommonIndex(char c){
        int index;
        if(c >= 'a' && c <= 'z'){
            index = c - 'a';
        }
        else if(c >= 'A' && c <= 'Z'){
            index = c - 'A';
        }
        else{
            index = c - '0' + 26;
        }
        
        return index;
    }
public:
    bool isPalindrome(string s) {
        int n = s.length();
        int i = 0, j = n-1;
        bool isOk = true;
        int left, right;
        while(i < j){
            while(i < n && !(s[i] >= '0' && s[i] <= '9') && !(s[i] >= 'a' && s[i] <= 'z') && !(s[i] >= 'A' && s[i] <= 'Z')){
                ++i;
            }
            
            while(j >= 0 && !(s[j] >= '0' && s[j] <= '9') && !(s[j] >= 'a' && s[j] <= 'z') && !(s[j] >= 'A' && s[j] <= 'Z')){
                --j;
            }

            if(i >= j){
                break;
            }
            
            left = getAlphanumericCommonIndex(s[i]);
            right = getAlphanumericCommonIndex(s[j]);

            
            if(left != right){
                isOk = false;
                break;
            }
            
            ++i;
            --j;
        }
        
        return isOk;
    }
};

int main() {
	Solution sol;
	cout << sol.isPalindrome("A man, a plan, a canal: Panama") << endl;
	cout << sol.isPalindrome("race a car") << endl;
	return 0;
}

using System;

namespace LeetCode125
{
	public class Solution {
	    private int GetAlphanumericCommonIndex(char c){
	        int index;
	        if(c >= 'a' && c <= 'z'){
	            index = c - 'a';
	        }
	        else if(c >= 'A' && c <= 'Z'){
	            index = c - 'A';
	        }
	        else{
	            index = c - '0' + 26;
	        }
	        
	        return index;
	    }
	    
	    public bool IsPalindrome(string s) {
	        int n = s.Length;
	        int i = 0, j = n-1;
	        bool isOk = true;
	        int left, right;
	        while(i < j){
	            while(i < n && !(s[i] >= '0' && s[i] <= '9') && !(s[i] >= 'a' && s[i] <= 'z') && !(s[i] >= 'A' && s[i] <= 'Z')){
	                ++i;
	            }
	            
	            while(j >= 0 && !(s[j] >= '0' && s[j] <= '9') && !(s[j] >= 'a' && s[j] <= 'z') && !(s[j] >= 'A' && s[j] <= 'Z')){
	                --j;
	            }
	
	            if(i >= j){
	                break;
	            }
	            
	            left = GetAlphanumericCommonIndex(s[i]);
	            right = GetAlphanumericCommonIndex(s[j]);
	
	            
	            if(left != right){
	                isOk = false;
	                break;
	            }
	            
	            ++i;
	            --j;
	        }
	        
	        return isOk;
	    }
	}
	
	public class Program
	{
		public static void Main()
		{
			Solution sol = new Solution();
			Console.WriteLine(sol.IsPalindrome("A man, a plan, a canal: Panama"));
			Console.WriteLine(sol.IsPalindrome("race a car"));
			Console.Read();
		}
	}
}