首页 > 专题系列 > Java解POJ > POJ 1159 Palindrome [解题报告] Java
2013
11-09

POJ 1159 Palindrome [解题报告] Java

Palindrome

问题描述 :

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.

As an example, by inserting 2 characters, the string “Ab3bd” can be transformed into a palindrome (“dAb3bAd” or “Adb3bdA”). However, inserting fewer than 2 characters does not produce a palindrome.

输入:

Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.

输出:

Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.

样例输入:

5
Ab3bd

样例输出:

2

解题代码:

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

public class Main {

 public static void main(String[] args) throws Exception{
	BufferedReader in = new BufferedReader(new InputStreamReader (System.in));
	int total = Integer.parseInt(in.readLine());
	String string = in.readLine();
		System.out.println(total-LCS(string,new StringBuffer(string).reverse().toString()));
}

//返回两个string的lcs的长度
public static int LCS(String str1,String str2){
	short length1 = (short)str1.length();
	short length2 = (short)str2.length();
	short[][]result = new short [length1+1][length2+1];
	for(int i=0;i< length1;i++){
		result[i][0] = 0;
	}
	for(int i=0;i< length2;i++){
		result[0][i] = 0;
	}
	for(int i=1;i<=length1;i++){
      for(int j=1;j<=length2;j++){
		if(str1.charAt(i-1)==str2.charAt(j-1))
		 result[i][j] = (short)(result[i-1][j-1]+1);
		else
         result[i][j] = result[i-1][j]>result[i][j-1]?result[i-1][j]:result[i][j-1];
		}
	}
	return result[length1][length2];
 }
	

}

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!