LeetCode 125. Valid Palindrome

125. Valid Palindrome

문제

팰린드롬은 모든 대문자를 소문자로 변환하고 영숫자가 아닌 모든 문자를 제거한 후에도 앞으로 읽을 때와 뒤에서 읽었을 때 동일한 경우를 말합니다. 여기서 영숫자 문자란 무낮와 숫자를 의미합니다.

문자열 s가 주어졌을 때 s가 팰린드롬이면 true를 리턴하고 그렇지 않으면 false를 리턴하세요.

Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:
Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

1차 시도 (37분 소요)

1. 주어진 문자열 s를 우선 소문자로 변환이 필요
2. 주어진 문자열에서 영어와 숫자만 남도록 필터링 필요
3. 배열을 이용하고 싶지만 주어진 문자열에서 영어와 숫자가 얼마나 존재할지 확신할 수 없으니 ArrayList를 사용한다.

class Solution {
    public boolean isPalindrome(String s) {
        List<Character> list = new ArrayList<>();

        for (char c: s.toCharArray()) {
            if (Character.isAlphabetic(c) || Character.isDigit(c)) {
                list.add(Character.toLowerCase(c));
            }
        }
        
        return true;
    }
}

위의 코드는 Example3의 경우에는 통과하지 못할 것 같다는 생각이 든다. 문자열이 모두 빈문자열일 경우 처리하는 코드의 추가가 필요할 것 같다.

class Solution {
    public boolean isPalindrome(String s) {
		// 빈문자로만 이루어져있을 경우 바로 true를 리턴
        if (s.trim().isEmpty()) {
            return true;
        }

        List<Character> list = new ArrayList<>();

        for (char c: s.toCharArray()) {
            if (Character.isAlphabetic(c) || Character.isDigit(c)) {
                list.add(Character.toLowerCase(c));
            }
        }

		return true;
    }
}

이제 문자열 s가 팰린드롬 문자열인지 아닌지 확인해야한다. 우선 두 가지 생각이 들었다.

1. 기존 리스트 복사
   1. 기존에 필터링한 리스트를 이용하여 해당 리스트의 가장 마지막 인덱스 요소를 첫 번째 요소로 하는 새로운 리스트 생성 후 비교
2. Two Pointer
   1. 기존에 필터링한 리스트를 위한 두 개의 포인터를 생성
   2. 각 포인터는 가장 앞의 요소와 가장 뒤의 요소를 가리킨다.
   3. 반복문을 이용해서 각 이터레이션 마다 앞의 포인터는 뒤로 한 칸씩, 뒤의 포인터는 앞으로 한 칸씩 이동하면서 비교한 후 모든 이터레이션을 통과하면 해당 문자열은 팰린드롬이다.

Two Pointer를 이용해서 문제를 해결해본다.

class Solution {
    public boolean isPalindrome(String s) {
        if (s.trim().isEmpty()) {
            return true;
        }

        List<Character> list = new ArrayList<>();

        for (char c: s.toCharArray()) {
            if (Character.isAlphabetic(c) || Character.isDigit(c)) {
                list.add(Character.toLowerCase(c));
            }
        }

        int lt = 0;
        int rt = list.size() - 1;

        while(lt < rt) {
            if (list.get(lt) != list.get(rt)) {
                return false;
            }
            lt++;
            rt--;
        }

        return true;
    }
}

while(lt < rt) 이므로 10번째 인덱스에서의 비교는 진행되지 않는다. lt, rt 모두 같은 문자를 가리키고 있으므로 비교할 필요가 없다. 문자의 개수가 짝수개일때도 문제 없음

다른 풀이를 이용한 개선

나의 풀이는 주어진 String을 이용해서 조건에 맞는 새로운 리스트를 이용한다. 하지만 굳이 새로운 리스트를 이용하지 않아도 충분히 해당 문제를 해결할 수 있었다. 개선된 코드는 two pointer를 사용하는 건 같지만 주어진 문자열만을 이용해서 문제를 해결하기 때문에 시간복잡도나 공간복잡도 면에서 이점이 있다.

class Solution {
    public boolean isPalindrome(String s) {
        if (s.isEmpty()) {
            return true;
        }

        int lt = 0;
        int rt = s.length() - 1;

        while(lt < rt) {
            char leftChar = s.charAt(lt);
            char rightChar = s.charAt(rt);

			// leftChar가 문자나 숫자가 아니면 바로 포인터를 다음 위치로 이동시킨다.
            if (!Character.isLetterOrDigit(leftChar)) {
                lt++;
            // rightChar가 문자나 숫자가 아니면 바로 포인터를 다음 위치로 이동시킨다.
            } else if (!Character.isLetterOrDigit(rightChar)) {
                rt--;
             // leftChar, rightChar 모두 문자이거나 숫자일 경우 leftChar, rightChar 비교
            } else {
                if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
                    return false;
                }

                lt++;
                rt--;
            }
        }
        
        return true;
    }
}