.leetcode(125. Valid Palindrome)

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

 

1. 2022.01.24 시도

소요시간: 7분(3분 구상, 4분 코딩, 공간복잡도O(n)), 11분(공간복잡도O(1))

// 공간복잡도: O(n)
class Solution {
    public boolean isPalindrome(String s) {
        
        String filtered = "";
        for(int x=0; x<s.length(); x++) {
            if (('a' <= s.charAt(x) && s.charAt(x) <= 'z')
                || ('0' <= s.charAt(x) && s.charAt(x) <= '9')) {
                filtered += s.charAt(x);
            } else if ('A' <= s.charAt(x) && s.charAt(x) <= 'Z') {
                filtered += (char)(s.charAt(x) + ('a'-'A'));
            }
        }
        
        int left = 0;
        int right = filtered.length() -1; 
        while(left < right) {
            if (filtered.charAt(left) != filtered.charAt(right)) {
                return false;
            } 
            left++;
            right--;
        }
        
        return true;
    }
}

// 공간복잡도: O(1)
class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length()-1;
        
        while(left < right) {
            while(!isAlphanumeric(s.charAt(left))) {
                if (left >= right) {
                    return true;
                }
                left++;
            }
            
            while(!isAlphanumeric(s.charAt(right))) {
                if (left >= right) {
                    return true;
                }
                right--;
            }
            
            char l = converIfCapital(s.charAt(left));
            char r = converIfCapital(s.charAt(right));
            if (l != r) {
                return false;
            }
            
            left++;
            right--;
        }
        
        return true;
    }
    
    private boolean isAlphanumeric(char target) {
        if ('a'<= target && target <= 'z') {
            return true;
        }
        
        if ('0'<= target && target <= '9') {
            return true;
        }
        
        if ('A'<= target && target <= 'Z') {
            return true;
        }
        
        return false;
    }
    
    private char converIfCapital(char target) {
        if ('A'<= target && target <= 'Z') {
            return (char)(target + ('a'-'A'));
        }
        
        return target;
    }
}

풀이 접근 과정

일단 영문과 숫자를 변환해서 새로운 string으로 만들고 palidrome확인하면 되겠다 싶었다.
그렇게 되면 시간 복잡도 O(n), 공간 복잡도 O(n)정도로 풀 수 있었다.

풀고나서 공간을 안쓰고도 포인터를 이용하면 잘 풀 수 있겠다 싶어서 도전했다. 문자 혹은 숫자인지 판단하는 것과 대문자일때 소문자로 변형해주는 로직만 처리하니 술술 풀렸다.

 

느낀점

• string 문제를 풀 때 포인터로 left, right가 굉장히 유용하다. 두개의 포인터를 기본으로 생각하니 문제가 쉽게 풀린다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형