[LeetCode] 680. Valid Palindrome II - 문제풀이

Description

문자열s가 주어졌을때 최대 한개의 문자열이 지워졌을때 palindrome 인지 여부를 반환하는 문제입니다. palindrome 이란 문자열의 앞과 끝에서 읽었을때 모두 동일한 문자열을 뜻합니다.

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

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Constraints:

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

Solution 1. Two Pointers

public boolean validPalindrome(String s) {

    int start = 0;
    int end = s.length() - 1;

    while (start < end)  {
        // Found a mismatched pair - try both deletions
        if (s.charAt(start) != s.charAt(end)) {
            return (checkPalindrome(s, start, end - 1) || checkPalindrome(s, start + 1, end));
        }
        start++;
        end--;
    }
    return true;
}
private boolean checkPalindrome(String s, int start, int end) {
    while (start < end) {
        if (s.charAt(start) != s.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

양끝에 포인터를 두고 한글자씩 서로 같은지를 비교해서 Palindrome 여부를 반환하는 기본 checkPalindrome() 메서드를 만들어 줍니다.

그리고 원본 문자열에서 동일방식으로 검증하다가 서로 다른 문자가 나왔을 경우 앞글자를 삭제했을때 남은 문자열의 Palindrome여부, 뒷글자를 삭제했을때 Palindrome여부 중 하나라도 일치하면 true, 둘다 Palindrome가 아니라면 false를 반환합니다.

Reference

Valid Palindrome II - LeetCode