Leet Code - 125. Valid Palindrome(C++)

예제: Valid Palindrome

문제
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

풀이

KMP알고리즘(문자열 검색 알고리즘)을 사용해서 푸는 문제인가 싶었는데, 문제를 자세히 읽어보니 KMP 알고리즘을 사용하면 오히려 실이 될 것 같고(KMP 알고리즘이 단순 Palindrome 문자열을 찾는 알고리즘이 아니라고 생각했다.), 단순 반복문을 사용하는 것이 더 빨리 끝날 것이라 판단했다.

문자열의 시작과 끝에서 동시에 시작하며, alphanumeric(영숫자)에서만 1:1로 비교해가며 왼쪽과 오른쪽에 해당하는 인덱스에서 문자가 다르다면 false를 리턴해 주는 형태이다.

전체적인 소스코드는 아래와 같다.

소스 코드

class Solution {
public:
	bool isPalindrome(string s) {
		int left = 0;
		int right = s.size() - 1;

		while (left < right) {
			char lc = tolower(s[left]);
			char rc = tolower(s[right]);


			if (!((lc >= 'a' && lc <= 'z') || (lc >= '0' && lc <= '9'))) {
				left++;
			}
			else if (!((rc >= 'a' && rc <= 'z') || (rc >= '0' && rc <= '9'))) {
				right--;
			}
			else {
				if (lc != rc)
					return false;
				left++;
				right--;
			}
		}

		return true;
	}
};

풀이 후기

다른 사람들의 풀이를 보니, erase를 사용해서 아예 영숫자가 아닌 문자열을 제외하는 방법도 있었다. 적절하게 쓰면 요긴할 것 같다.