125. Valid Palindrome

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

Valid Palindrome - LeetCode

난이도 : easy

문제

주어진 문자열이 펠린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

만약 "A man, a plan, a canal: Panama" 문자열이 들어온다면

1. 알파뱃과 숫자만 추출한다. -> AmanaplanacanalPanama 

2. tolower 함수를 통해 소문자로 모두 변경한다. -> amanaplanacanalpanama 

3. 회문 여부를 체크 한다.

 

코드

string cand 라는 변수를 선언하였음으로 O(N)의 공간복잡도를 갖는다. 또한 시간 복잡도도 O(N) 이다. 

class Solution {
public:
    bool isPalindrome(string s) {
        string cand;
        
        // 문자열에서 알파벳만 추출 한다.
        for(char c:s) {
            if(isalnum(c)) {
                cand += tolower(c);
            }
        }
        
        int start = 0;
        int end = cand.size() - 1;
        
        bool ret = true;
        // start, end 로 문자열 요소의 처음과 끝을 비교한다 만약 다르다면 회문이 아니다.
        while(start <= end) {
            
            if(cand[start] == cand[end]) {
                start++;
                end--;
            }
            else {
                ret = false;
                break;
            }
        }
        
        return ret;
    }
};

 

시간복잡도 : O(nlogn)

STL sort 함수를 평균적인 시간복잡도로 가정했다.

pivot 정렬은 최악의 경우 O(N^2)이 걸릴 수 있다. ※random_suffle을 이용해서 재정리 하던가해야한다 이부분은 나중에 포스팅 하겠다.

class Solution {
public:
    bool isPalindrome(string s) {
        string cand;
        
        // 문자열에서 알파벳만 추출 한다.
        for(char c:s) {
            if(isalnum(c)) {
                cand += tolower(c);
            }
        }
        
        // stl reverse 함수를 통하여 문자열을 뒤집고 비교한다.
        // 같으면 true 아니면 false
        s = cand;
        reverse(cand.begin(), cand.end());
        return s == cand;
    }
};