[leetcode-680] Valid Palindrome II

1. 문제조건

 - Palindrome이란 앞에서 읽은것과 뒤에서 읽은것이 같은 문자열

 - 문자열 s는 not empty

 - a-z까지 소문자

 - 최대길이 50000

 - 문자열에서 최대 1개의 문자를 삭제 할 수 있음

2. 아이디어

가장 기본적인 아이디어는 재귀함수를 이용해서 팰린드롬인지를 검사하는 것 입니다. 양쪽 문자의 끝이 같다면 양쪽문자열을 제외한 문자열도 팰린드롬이어야 합니다. 하지만 문자를 최대 한개 삭제할 수 있다는 조건이 있기 때문에 이때 분기를 나눠서 재귀함수를 호출해야합니다. 각각의 재귀함수 결과를 '||' 조건으로 합치면 어느 하나가 true이면 결국 true가 반환됩니다. 또한 문자 삭제 횟수가 2회이상인 경우는 검사할 필요가 없으므로 false를 리턴해서 탐색 경우수를 줄이면됩니다.

class Solution {
    
    public boolean recurPalindrome(String s, int strtNum, int endNum, int deleteNum) {
    	
        if(deleteNum == 2) {
			return false;
		}
    	
    	if(strtNum == endNum || strtNum> endNum) {
    		return true;

    	} else{
    		
    		char strtChar = s.charAt(strtNum);
    		char endChar  = s.charAt(endNum); 
    		
    		if(strtChar == endChar) {           //왼쪽 오른쪽 같은 경우
    			
    			return recurPalindrome(s, strtNum+1, endNum-1, deleteNum);
    			
    		} else{     //왼쪽 오른쪽 다른 경우
    			
    			return recurPalindrome(s, strtNum+1, endNum, deleteNum+1) || recurPalindrome(s, strtNum, endNum-1, deleteNum+1);
    			
    		}
    		
    	} 

    }
    
    public boolean validPalindrome(String s) {
    	int deleteNum = 0;
    	int stringSize = s.length() -1;
    	
    	boolean answer = recurPalindrome(s, 0, stringSize, deleteNum);
    	
    	return answer;
    }
}

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

Valid Palindrome II - LeetCode