G17609. 회문

문제

제출 코드

• 사용 알고리즘 : 문자열

문자열의 양 끝에서부터 시작해서 중간지점에 닿을때까지 양 끝단의 문자열이 일치하는지 체크하였다.

양 끝단의 문자열이 다른 경우, 팰린드롬이 아니거나 둘중 하나의 문자열을 빼면 팰린드롬이 되거나로 나뉘게 된다.

아직 문자열을 빼보지 않은 상태의 경우엔 양 끝의 문자열을 하나씩 빼보면서 체크하지 않은 가운데 문자열들을 다시 확인해보도록 하였다.

package gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class G17609_palindrome {

	static int isPallindrome(String s, boolean chance) {
		char[] str = s.toCharArray();
		int first=0, last=str.length-1;

		while(true) {
			if(first>=last) {
				if (chance) return 0;
				else return 1;
			}
			else if(str[first]==str[last]) {
				first += 1;
				last -= 1;
			}else {
				if(chance) {
					return Math.min(isPallindrome(s.substring(first+1, last+1), false)
							, isPallindrome(s.substring(first, last), false));
				}else return 2;
			}
		}
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int t=0; t<T; t++) {
			System.out.println(isPallindrome(br.readLine(), true));
		}
	}

}