[Algorithms] palindrome 회문 단순코드

회문(완전탐색) 접근 방법

문자열의 길이를 N이라고 했을때, 앞에서 읽거나 뒤에서 읽거나 같은 문자열을 회문이라한다. 

1. 2n-1개의 문자열을 모두 탐색해서 각각이 회문이 되는지 탐색 -> 앞의n개의 문자가 일치하는것 찾기 

    이 방법은 구현은 쉽지만 시간 제한이 있을때 시간초과가 날 확률이 높다

 

2. 문자열에 추가할 n-1개의 문자열을 모두 탐색, 각각의 것이 회문이 되느지 확인하기

    n번째 문자가 고정되어 1번보다는 좋은 접근 방법이지만 문자열의 길이가 10000이면 9999번을 탐색하게된다. 

 

3. 2n-1의 회문을 완전탐색하고 앞의 n개의 문자가 일치하는것을 찾기 

    회문을 모두 찾는것은 힘들지만 모두 찾으면 n개의 문자가 ㅇ리치하는지 쉽게 확인할 수 있으며 그 중에서 문자열의      길이가 가장 짧은 것을 선택하면된다. 

 

회문을 생성할 수 있는 최소길이 출력 하는 코드 

package TopCoder;

public class Palindrome {
	public static void main(String[] args) {
		String s = "abab";
		for(int i =s.length(); ;i++ ) {
			boolean flag = true;
			for(int j =0 ;j<s.length(); j++) {
				if((i-j-1)<s.length() && s.charAt(j)!=s.charAt(i-j-1)) {
					flag = false;
					break;

				}//if
			}//j for문
			
			if(flag) {
				System.out.println(i);
				break;
			}
		}
	}
}