[LeetCode] 125번 (Valid Palindrome)

https://leetcode.com/problems/valid-palindrome/?envType=study-plan-v2&envId=top-interview-150

Valid Palindrome - LeetCode

---

🤣 문제 설명

• 하나의 문자열이 주어질 때, 영문자를 제외한 모든 문자를 제거하고 모든 영문자를 소문자로 바꿨을 때 해당 문자열이 회문이지 아닌지 여부를 구하여라.
• 입력 : String s
• 출력 : boolean type (true or false)
• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

 

🥲 문제 해결

• toLowerCase() 를 통해 소문자로 변경한다.
• replaceAll() 과 정규표현식을 통해, 소문자가 아닌 모든 문자를 제거한다.
• 반복문을 돌며, 문자열의 앞과 뒤를 비교한다. 모든 비교가 끝나면 true 하나라도 틀릴 시 false 를 반환한다.

 

🙂 시간복잡도

탐색을 하며 소문자로 바꾸고, replaceAll() 과 같은 함수가 O(n)이다.

 

🙃 공간복잡도

O(1) 이다.

 

😉 정답

class Solution {
    public boolean isPalindrome(String s) {
        String newStr = s.toLowerCase();
        newStr = newStr.replaceAll("[^a-z0-9]", "");

        int n = newStr.length();
        for(int i=0; i<n/2; i++) {
            if(newStr.charAt(i) != newStr.charAt(n-i-1)) {
                return false;
            }
        }

        return true;
    }
}

 

😗 개선하기

• 찾아보니 Character 에는 isLetterOrDigit() 이라는 메서드가 있다. 해당 메서드를 통해 문자 숫자인지, 특수문자인지를 확인할 수가 있다.
• 또한 length/2 로 반복문을 도는게 아닌, start 와 last 포인터 2개를 두고 start 가 last 를 앞서기 전까지 반복문을 돌며 문자를 확인하는 방법도 있다.
• 해당 알고리즘과 내가 푼 알고리즘을 비교하면, 뭐가 더 개선된 알고리즘인지는 확신이 안 서지만, 밑 알고리즘이 좀 더 직관적인것 같다.

class Solution {
    public boolean isPalindrome(String s) {
        if (s.isEmpty()) {
        	return true;
        }
        int start = 0;
        int last = s.length() - 1;
        while(start <= last) {
        	char currFirst = s.charAt(start);
        	char currLast = s.charAt(last);
        	if (!Character.isLetterOrDigit(currFirst )) {
        		start++;
        	} else if(!Character.isLetterOrDigit(currLast)) {
        		last--;
        	} else {
        		if (Character.toLowerCase(currFirst) != Character.toLowerCase(currLast)) {
        			return false;
        		}
        		start++;
        		last--;
        	}
        }
        return true;
    }