[LeetCode] C++ 125. Valid Palindrome

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

 

문제

 

풀이

1. ASCII 문자에 해당하는 글자만 남긴 뒤, 소문자로 바꾸자

2. Palindrome이 성립하는지 순서대로 비교해보고 비교 중 다른 문자가 있다면 false를 반환하고, 나머지는 true를 반환하자

 

풀이 1

#include <algorithm> // std::remove_if
#include <string>
#include <cctype> // std::isalnum, std::tolower

class Solution {
private:
    bool is_not_alnum(char c) {
        return !isalnum(static_cast<unsigned char>(c));
    }

    string preprocess(string s){
        s.erase(remove_if(s.begin(),s.end(), [this](char c) { return is_not_alnum(c); }), s.end());
        for (auto& c: s){
            c = tolower(c);
        }
        return s;
    }
public:
    bool isPalindrome(string s) {
        s = preprocess(s);
        int len = s.length();
        for (int i = 0; i < len; ++i){
            if(s[i] != s[len - i - 1])
                return false;
        }

        return true;
    }
};

 

풀이 2

풀이코드 1의 경우 처음부터 문자열 전체를 전처리한다. 만약 palindrome 검사 초반에 false라는 결론이 난다면, 나머지 것들은 불필요하게 전처리하느라 시간을 낭비했을 것이라고 판단했다. 따라서 투 포인터 방식으로 수정을 해보았다. 

using namespace std;

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

        while (left < right) {
            while (left < right && !isalnum(static_cast<unsigned char>(s[left]))) {
                ++left;
            }
            while (left < right && !isalnum(static_cast<unsigned char>(s[right]))) {
                --right;
            }
            if (tolower(static_cast<unsigned char>(s[left])) != tolower(static_cast<unsigned char>(s[right]))) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};

메모리 부분에서는 효율이 증가했지만 속도는 감소하였다. 문자열의 길이가 예상했던 것 만큼 큰 테스트 케이스가 많이 없거나, 긴 문자열에 대해서 palindrome이 성립하는 테스트 케이스들이 있지않았을까라는 생각을 했다.

 

풀이 3

using namespace std;

class Solution {
public:
    bool isPalindrome(string s) {
        int bias_left = 0;
        int bias_right = 1;
        int str_len = s.length();

        for(int i = 0; i < s.length(); ++i){
           while(!isalnum(s[i + bias_left])){
            bias_left++;
            if(i+bias_left == str_len)
                return true;
           }
           while(!isalnum(s[str_len - i - bias_right])){
            bias_right++;
           }

            if(i + bias_left >= str_len - i - bias_right)
                break;
        
            if (tolower(s[i+bias_left]) != tolower(s[str_len - i - bias_right]))
                return false;
        }
        return true;
    }
};

 

빠른 풀이

기본 배열을 사용할 때는 중간 위치에서의 추가, 제거가 오래 걸리기 때문에 새로운 임시 string에 추가하는 방법을 사용하면 빠르게 실행 가능했다. 인덱스 위치 또한 계속 검사하다 보니까 테이트 케이스가 복잡하지 않은 경우에는 시간이 더 오래 걸렸던 것 같다. 아예 새로운 문자열을 만든 뒤에서는 인덱스를 계산하지 않아도 되기에 더 빠르게 개선할 수 있었던 것 같다. 그리고 기존 코드들은 전체를 다 검사했는데 그렇게 하니까 중복되서 같은 거를 검사하는 꼴이 된다. 예를 들면 s[2] 와 s[6]을 검사했는데 s[6]과 s[2]를 검사해버린 것이다. 그래서 절반까지만 검사해도 충분하므로 코드를 이에 맞추어 변경했다.

using namespace std;

class Solution {
public:
    bool isPalindrome(string s) {
        string temp="";
        for(int i = 0; i < s.length(); ++i){
            if((s[i]>='a'&& s[i]<='z') || (s[i]>='A' && s[i] <= 'Z') || isdigit(s[i])){
                temp+=tolower(s[i]);
            }
        }

        int len = temp.length();
        for (int i = 0; i < len / 2 ; ++i){
            if(temp[i] != temp[len - i - 1]){
                return false;
            }
        }
        return true;
    }
};