[006]Valid Palindrome

 

문제: https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3411/

---

팰린드롬 찾기 문제입니다. 숫자와 영문자를 제외한 나머지 문자는 제외하고 팰린드롬인가를 물어보는 문제입니다.

 

맨 처음에 재귀로 풀었는데 생각보다 테케 문자열이 깁니다. 그러므로 재귀로 풀면 TLE이 납니다.

 

그래서 저는 deque를 활용하여 팰린드롬을 체크하였습니다. 

 

HEAD와 TAIL이 일치하면 계속 빼주다가 deque 사이즈가 1 또는 비게 되면 그 문자열은 팰린드롬입니다.

class Solution {
public:
    deque<char> dq;
    
    bool isPalindrome(string s) {
        string pureStr = "";
        for (int i = 0; i < s.size(); ++i) {
            if ('a' <= s[i] && s[i] <= 'z') {
                pureStr += s[i];
            }
            else if ('0' <= s[i] && s[i] <= '9') {
                pureStr += s[i];
            }
            else if ('A' <= s[i] && s[i] <= 'Z') {
                pureStr += ((s[i] - 'A') + 'a');
            }
        }
        
        if (pureStr.compare("") == 0) return true;
        else {
            for (int i = 0; i < pureStr.size(); ++i)
                dq.push_back(pureStr[i]);
            
            while (!dq.empty() && dq.size() != 1) 
            {
                char head = dq.front();
                char tail = dq.back();
                dq.pop_front();
                dq.pop_back();
                if (head != tail) {
                    return false;
                } 
            }
            return true;
        }
    }
};