(알고리즘) 팰린드롬 분할

private static boolean isPaline[][];
private static int []dp;
public static void main(String[] args) {
// TODO Auto-generated method stub
try(BufferedReader reader=new BufferedReader(new InputStreamReader(System.in))){


char[] words=reader.readLine().toCharArray();
isPaline=new boolean[2501][2501];
dp=new int[2501];
Arrays.fill(dp,-1);
int len=words.length;
for(int i=0;i<len;i++){
isPaline[i][i]=true;
for(int j=0;j<i;j++){
if(words[i]==words[j])isPaline[i][j]=isPaline[i-1][j+1];
if(i-j==1){
isPaline[i][j]|=words[i]==words[i-1];
}
}
}
System.out.println(solve(len-1));
}catch(IOException e){
e.printStackTrace();
}
}
private static int solve(int pos){
if(pos<0)
return 0;
int r=dp[pos];
if(r!=-1)return r;
r=Integer.MAX_VALUE;
for(int i=pos;i>=0;i--){
if(isPaline[pos][i]){
r=Math.min(r,1+solve(i-1));
}
}
return r;
}

댓글

이 블로그의 인기 게시물

(ElasticSearch) 결과에서 순서 정렬

(18장) WebSocekt과 STOMP를 사용하여 메시징하기

(네트워크)폴링방식 vs 롱 폴링방식