【LeetCode】125.Valid Palindrome(验证回文串)-C++实现

本题是Facebook、Microsoft、Uber、Zenerfits的面试题。 

题目描述：

 

一、第一种方法

（1）使用双指针，i 和 j 同时遍历：

	bool isPalindrome(string s) {

		int i = next_alpha_numeric(s, 0);
		int j = prev_alpha_numeric(s, (int)s.size() - 1);
		while (i <= j) {
			if (tolower(s[i]) != tolower(s[j])) //tolower:将大写字母转换为小写
				return false;
			i = next_alpha_numeric(s, i + 1);
			j = prev_alpha_numeric(s, j - 1);
		}
		return true;
	}

（2）检查s[i]是十进制数字还是大写或小写字母：

	int next_alpha_numeric(const string& s, int index) {
		for (int i = index; i < s.size(); i++)
			if (isalnum(s[i]))  //检查s[i]是十进制数字还是大写或小写字母
				return i;
		return (int)s.size();
	}

（3）检查s[j]是十进制数字还是大写或小写字母:

	int prev_alpha_numeric(const string& s, int index) {
		for (int i = index; i >= 0; i--)
			if (isalnum(s[i]))
				return i;
		return -1;
	}

（4）完整源代码：

#include <iostream>

using namespace std;


/// Two Pointers
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {

public:
	bool isPalindrome(string s) {

		int i = next_alpha_numeric(s, 0);
		int j = prev_alpha_numeric(s, (int)s.size() - 1);
		while (i <= j) {
			if (tolower(s[i]) != tolower(s[j])) //tolower:将大写字母转换为小写
				return false;
			i = next_alpha_numeric(s, i + 1);
			j = prev_alpha_numeric(s, j - 1);
		}
		return true;
	}

private:
	int next_alpha_numeric(const string& s, int index) {
		for (int i = index; i < s.size(); i++)
			if (isalnum(s[i]))  //检查s[i]是十进制数字还是大写或小写字母
				return i;
		return (int)s.size();
	}

	int prev_alpha_numeric(const string& s, int index) {
		for (int i = index; i >= 0; i--)
			if (isalnum(s[i]))
				return i;
		return -1;
	}
};


void print_bool(bool res) {
	cout << (res ? "True" : "False") << endl;
}

int main() {

	string s1 = "A man, a plan, a canal: Panama";
	print_bool(Solution().isPalindrome(s1));

	string s2 = "race a car";
	print_bool(Solution().isPalindrome(s2));

	system("pause");
	return 0;
}

二、第二种方法

  将第一种方法更加简单化：

  两个索引指针，分别从左端点和右端点开始，跳过非字母数字的字母。一旦发现不匹配，函数立即返回false，否则当两个索引指针在中间相遇时，匹配返回true。

bool isPalindrome(string s) {
	for (int i = 0, j = s.size() - 1; i < j; i++, j--) { // 从前端和末端分别移动i 和 j指针，直到它们发生碰撞
		
        int n = s.size();
        if (n == 1) return true;

		while (isalnum(s[i]) == false && i < j) 
			i++; // 如果不是字母数字,增量左指针
		while (isalnum(s[j]) == false && i < j) 
			j--; // 如果不是字母数字,递减右指针
		
		if (toupper(s[i]) != toupper(s[j])) 
			return false; // 如果不匹配,则退出并返回false
	}

	return true;
}

第三种方法：

  任何大写字母和小写字母之间的ASCII代码的区间在32.例如，'A'是65而'a'是97.所以我们可以在比较字母时使用它。

inline bool chk(char a) {
        return ((a >= 'a') && (a <= 'z')) ||                 
               ((a >= 'A') && (a <= 'Z')) ||                 
               ((a >= '0') && (a <= '9')) ;
    }

双指针遍历：

class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size();
        if (n == 1) return true;
        int i = 0, j = n - 1;
        while (i <= j) { // two pointers not met yet
            // ignore other characters from beginning
            while ((i <= j) && (!chk(s[i]))) i ++;              
            // ignore other characters from end             
            while ((j >= i) && (!chk(s[j]))) j --; 
            // not equal return invalid
            if ((i < j) && (s[i] != s[j]) && (s[i] != s[j] + 32) && (s[j] != s[i] + 32)) return false;
            i ++;
            j --;
        }
        return true;
    }
};

<本文完>

参考资料：

1）刘宇波的github

2)LeetCode-Discuss 

3）https://helloacm.com/coding-exercise-valid-palindrome-c-online-judge/