[LeetCode] 125. Valid Palindrome

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

개요

1. 주어지는 문자열이 회문인지 판단해라
   • 영어, 숫자가 아닌 모든 문자는 무시한다.
   • 대소문자 구분 안함

문제 해결 아이디어

• 회문은 뒤에서부터 읽는 것과 앞에서부터 읽는 것과 동일하다.
  ➡️ 포인터를 앞 뒤로 둬서 순차적으로 짝이 맞는지 검사하자

🧐 투 포인터를 이용하자

의사 코드

1. 왼쪽 인덱스와 오른쪽 인덱스를 가르키는 포인터를 선언한다.
2. 각 포인터를 움직여서 문자열 s를 순차적으로 검사한다.
3. s의 왼쪽 인덱스 문자가 유효한 문자가 아니다 (조건)
   3-1. 왼쪽 인덱스 값을 1 증가시킨다.
4. s의 오른쪽 인덱스 문자가 유효한 문자가 아니다 (조건)
   4-1. 오른쪽 인덱스 값을 1 감소시킨다.
5. 왼쪽 인덱스 문자가 오른쪽 인덱스 문자와 동일하다 (조건)
   5-1. 왼쪽 인덱스 값 1 증가시킨다.
   5-2. 오른쪽 인덱스 값 1 감소시킨다.
6. 왼쪽 인덱스 문자가 오른쪽 인덱스 문자와 다르다. (조건)
   6-1. false 를 반환한다.

left = 0
right = 마지막 인덱스
while(left < right){
	왼쪽 문자 = s.charAt(left)
    오른쪽 문자 = s.charAt(right)
	if(왼쪽 문자가 유효하지 않음){
    	left++
        continue
   }
   if(오른쪽 문자가 유효하지 않음){
    	right--
        continue
   }
   
   if(a == b) {
   		left++
        right--
   } else {
   		return false
   }
   
}
return true

결과

전체 코드 github 링크

다른 풀이

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;
    }

Character.isLetterOrDigit() 이라는 java 내장 함수가 있어서 이걸 활용하면 좀 더 간결하게 코드를 작성할 수 있을 것 같다.
또 왼쪽 문자와 오른쪽 문자가 동일한지 체크하는 로직을 else 문 뒤에 넣어 continue 없이 while 문을 구성했다.