[LeetCode] 125. Valid Palindrome

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

Valid Palindrome - LeetCode

 

유효한 팰린드롬을 확인하는 문제입니다.

String s가 주어지면 알파벳, 숫자를 제외한 모든 letters를 제외하고 나서

팰린드롬이 맞는지 확인하는 문제입니다.

 

문제접근

처음 문제를 주어진 조건에 맞게 구현해나가는 식으로 접근하였습니다.

toLowerCase를 활용하여 소문자로 바꿔주고

loop를 사용해 알파벳, 숫자인 letters들만 선택하여 StringBuilder에 담았습니다.

 

그리고 reverse함수를 이용해 문자를 반전시켜 유효한 팰린드롬인지 확인하였습니다.

 

   public boolean isPalindrome(String s) {
        final String lowerS = s.toLowerCase();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < lowerS.length(); i++) {
            if (lowerS.charAt(i) >= 'A' && lowerS.charAt(i) <= 'Z' || lowerS.charAt(i) >= 'a' && lowerS.charAt(i) <= 'z') {
                sb.append(lowerS.charAt(i));
            }
            if (lowerS.charAt(i) >= '0' && lowerS.charAt(i) <= '9') {
                sb.append(lowerS.charAt(i));
            }
        }

        String result = sb.toString();
        String reverse = sb.reverse().toString();
        return reverse.equals(result);
    }

   

시간복잡도

시간복잡도는 주어진 String을 한번은 무조건 탐색해야 합니다.

그리고 그외에 시간을 더 사용하는 로직이 없으므로 O(n)의 시간복잡도가 필요합니다.

 

다른사람의 풀이

투포인터를 이용하여 푸는 방법이 있습니다.

또한 isLetterOrDigit을 사용해 문자와 숫자를 한번에 확인할 수 있었습니다.

 

public boolean isPalindrome(String s) {       
        int i = 0, j = s.length() - 1;
        char[] chars = s.toLowerCase().toCharArray();

        while (i <= j) {
            if (!Character.isLetterOrDigit(chars[i])) {
                i++;
            } else if (!Character.isLetterOrDigit(chars[j])) {
                j--;
            } else if(chars[i++] != chars[j--]) {
                return false;
            }
        }

        return true;
    }

 

느낀점

배열을 확인하면서 2개의 값을 비교할때는 투포인터를 활용할 생각을 해야겠습니다.

 

참고

[LeetCode Easy] Valid Palindrome (Java)