LeetCode | Easy | 680. Valid Palindrome II

LeetCode | Easy | 680. Valid Palindrome II

Problems

• 📘 Src: LeetCode
• 🗂️ Cat: Two Pointers

Description

Given a string s, return true if the string can be a palindrome after deleting at most one character from it.

Constraints

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.

Examples

s	Output
"aba"	true
"abca"	true
"abc"	false

Solutions

• ⏳ TC: O(n)
• 💾 SC: O(1)

import java.util.*;

class Solution {

    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;

        // 문자열의 양 끝에서 중앙으로 이동하며 비교
        while (left < right) {
            // 문자가 일치하지 않으면 한 문자를 제외하고 회문인지 확인
            if (!isEquals(s, left, right)) {
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true; // 모든 문자가 일치하면 회문
    }

    // 부분 문자열이 회문인지 확인하는 메서드
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            // 문자가 일치하지 않으면 회문이 아님
            if (!isEquals(s, left, right)) {
                return false;
            }
            left++;
            right--;
        }
        return true; // 모든 문자가 일치하면 회문
    }

    // 두 문자가 같은지 확인하는 메서드
    private boolean isEquals(String s, int left, int right) {
        return s.charAt(left) == s.charAt(right);
    }
}

Approaches

이 문제는 주어진 문자열 s에서 최대 하나의 문자를 삭제하여 회문으로 만들 수 있는지 확인하는 문제입니다. 투 포인터를 사용하여 문자열의 양 끝에서 중앙으로 이동하며 비교하는 방식으로 해결할 수 있습니다.

문제를 해결하는 과정은 다음과 같습니다:

• 문자열 s의 좌측과 우측에서 시작하는 두 개의 포인터를 초기화합니다.
• 좌측 포인터가 우측 포인터보다 작을 때까지 반복합니다:
  • 두 포인터가 가리키는 문자가 같지 않은 경우, 좌측 포인터를 하나 증가시키거나 우측 포인터를 하나 감소시킨 문자열이 회문인지 확인합니다. 이 때 isPalindrome() 메서드를 사용하여 한 문자를 삭제한 후의 부분 문자열이 회문인지 확인합니다.
• isPalindrome() 메서드는 주어진 부분 문자열이 회문인지 확인합니다. 이를 통해 한 문자를 삭제한 후에도 회문인지 검사할 수 있습니다. 문자열의 길이가 짝수인 경우, 마지막 문자들인 left와 right가 교차하면 둘 중 하나만 삭제해도 회문 조건을 만족하기 때문에 참을 반환합니다.
• 반복이 끝날 때까지 모든 문자가 일치하면 문자열 s는 회문입니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)로 매우 효율적입니다.

Attempts

처음에는 문자열을 뒤집어서 직접 비교하는 방법을 사용했습니다. 하지만 이 접근법은 공간 복잡도 측면에서 비효율적이었습니다. 이를 구현한 코드는 아래와 같습니다:

import java.util.*;

class Solution {

    public boolean validPalindrome(String s) {
        if (reverse(s).equals(s)) return true;
        
        int left = 0;
        int right = s.length() - 1;

        for (int i = 0; i < s.length() / 2; i++) {
            if (!isMatch(s.charAt(left), s.charAt(right))) {
                return compare(s, left) || compare(s, right);
            }

            left++;
            right--;
        }

        return false;
    }

    private boolean isMatch(char left, char right) {
        return left == right;
    }

    private boolean compare(String s, int index) {
        String removed = remove(s, index);
        return reverse(removed).equals(removed);
    }

    private String remove(String s, int index) {
        StringBuilder sb = new StringBuilder(s);
        return sb.deleteCharAt(index).toString();
    }

    private String reverse(String s) {
        StringBuilder sb = new StringBuilder(s);
        return sb.reverse().toString();
    }
}

이 방식은 다음과 같은 절차로 이루어집니다:

• 문자열이 이미 회문인지 확인하기 위해 문자열을 뒤집어 비교합니다.
• 좌우 포인터를 사용하여 문자열을 순회합니다.
• 문자가 일치하지 않으면 해당 문자를 제거한 후 나머지 문자열이 회문인지 확인합니다.
• 문자열을 한 글자 제거한 후 회문인지 확인하기 위해 문자열을 뒤집습니다.

이 접근 방식은 문자열을 뒤집고 비교하는 과정에서 많은 메모리를 사용하여 공간 복잡도가 높아지는 문제가 있었습니다.

효율성 측면에서 개선된 최종 알고리즘은 투 포인터를 사용하여 문자열을 직접 비교하며, 필요 시 한 문자를 제외하고 회문 여부를 확인하는 방식으로 구현되었습니다. 이를 통해 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 최적화되었습니다.