LeetCode : 125. Valid Palindrome

문제 링크

문제 먼저 읽기

• 어떤 문자 s가 주어질 때, Palindrome 조건인 문자열이면 ture를 반환합니다.
• Palindrome 는 모든 대문자를 소문자로 변환 후 영어 혹은 숫자가 아닌 문자를 제거한 후 앞뒤가 같은 문자를 말합니다.

Input: s = "A man, a plan, a canal: Panama"
Output: true

 

어떻게 풀까?

생각

• 양 끝부터 중앙으로 향하는 포인터를 사용하여 다른 것이 나오면 false를 반환해보면 어떨까?
  • 이경우 시간복잡도 O(n/2)가 될 것이라 예상됩니다.
• 영어나 숫자가 아닌 다른 문자가 나오면 다음으로 문자를 가르키도록 합니다.

 

수도코드

class Solution {
    public boolean isPalindrome(String s) {
        int pointerS = 0; // s의 시작지점
        int pointerE = s.length() -1; // s의 마지막 지점
        
        while (pointerS < pointerE) {
            if (!Character.isLetterOrDigit(s.charAt(pointerS))) {
                pointerS ++;
            }
            if (!Character.isLetterOrDigit(s.charAt(pointerE))) {
                pointerE --;
            }

            if (Character.toLowerCase(s.charAt(pointerS)) != Character.toLowerCase(s.charAt(pointerE))) {
                return false;
            }
            
            pointerS ++; // 다음 포인터로 이동
            pointerE --;
        }
        return true;
    }
}

• 이 코드는 테스트 코드를 통과하지 못했다. 발견한 오류는 pointer를 옮기더라도 영어대소문자나 숫자가 아닌 문자가 나올 수 있다는 것입니다.

2차 수도코드

class Solution {
    public boolean isPalindrome(String s) {
        int pointerS = 0; // s의 시작지점
        int pointerE = s.length() -1; // s의 마지막 지점
        
        while (pointerS < pointerE) {
            
						// 문자나 숫자를 만날 때까지 이동
            while (pointerS < pointerE && !Character.isLetterOrDigit(s.charAt(pointerS))) {
                pointerS++;
            }
            while (pointerS < pointerE && !Character.isLetterOrDigit(s.charAt(pointerE))) {
                pointerE--;
            }
            
            if (Character.toLowerCase(s.charAt(pointerS)) != Character.toLowerCase(s.charAt(pointerE))) {
                return false;
            }
            
            pointerS++;
            pointerE--;
        }
        
        return true;
    }
}

결과

<aside> 💡 Success

Runtime: 2 ms, faster than 99.65% of Java online submissions for Valid Palindrome.

Memory Usage: 42 MB, less than 73.29% of Java online submissions for Valid Palindrome.

</aside>

 

다른 풀이 방식과 문제 회고

class Solution {
    public boolean isPalindrome(String s) {
        int sLen = s.length();
        int i = 0,j = sLen-1;
        while(i<=j){
            int frontC = (int)s.charAt(i);
            int backC = (int)s.charAt(j);
            if(!((frontC<58 && frontC >=48) ||(frontC<=90 && frontC>=65) || (frontC<=122 && frontC>=97))){
                i+=1;
            }else if(!((backC<58 && backC >=48) ||(backC<=90 && backC>=65) || (backC<=122 && backC>=97))){
               j-=1;
            }else{
                if((frontC==backC) || ((frontC>64 && backC>64) && (((frontC+32)==backC) || ((frontC-32)==backC))))
                {
                    i +=1;
                    j -=1;
                }else{
                    return false;
                }
            }
        }
        return true;
        
    }
}

• 별도 메서드를 사용하지 않고, 정수를 비교하는 편이 더 빠른 것 같습니다.

class Solution {
    public boolean isPalindrome(String s) {

        String a=s.replaceAll("[!#$%&'()*+,-./:;<=>?@^_`{|}~\\\\\\\\\\"\\\\[\\\\] ]*", "");
        StringBuilder res= new StringBuilder(a);
        res=new StringBuilder(res.toString().trim().toLowerCase());
    
        String dup= res.toString();

        StringBuilder res1= new StringBuilder(dup);
        res1.reverse();
        String org= res1.toString();

        return(dup.equals(org));
               
    }
}

• 반면 정규식을 사용할 경우 공간 복잡도 면에서 유리한 것을 확인할 수 있었습니다.