[POJ]1159 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. 

题意是要求最少插入多少个字符，可以让输入串变成回文。标准的DP问题，如果我们用dp[i][j]表示最少插入的字符数可以让子串s[i:j]变成回文，我们可以求得递推公式：

• dp[i][j] = dp[i + 1][j - 1], if s[i] == s[j]
• dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1

空间复杂度和时间复杂度都为O(n^2)，n为输入子串的长度。代码如下：

	//POJ 1159
	//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.
	#include<iostream>
	#include<algorithm>
	#include<stdlib.h>
	#include<stdio.h>
	#include<iomanip>
	#include<string.h>
	using namespace std;
	const int MAX=5005;
	int len;
	char s[MAX];
	short int dp[MAX][MAX];//will MLE if not intialize as short array
	int main()
	{
	cin.sync_with_stdio(false);
	while (cin >> len)
	{
	cin >> s;
	//dp[i][j] represents minimum inserted chars required to make substr[i, j] to be palindrome
	//dp[i][j] = dp[i + 1][j - 1], if s[i] == s[j]
	//otherwise, dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
	memset(dp, 0, sizeof(dp[0][0]) * MAX * MAX);
	for(int k = 2; k <= len; ++k)
	{
	for(int i = 0; i <= len - k; ++i)
	{
	if(s[i] == s[i + k - 1])dp[i][i + k - 1] = dp[i + 1][i + k - 2];
	else dp[i][i + k - 1] = min(dp[i + 1][i + k - 1], dp[i][i + k - 2]) + 1;
	}
	}
	cout << dp[0][len - 1] << endl;
	}
	return 0;
	}

view raw POJ_1159_Palindrome_dp.cpp hosted with ❤ by GitHub

另一种做法，对于给定输入的字符串s，如果其最长的回文子序列为p，那么其剩余没有对应字符能形成回文的字符的数量为len(s) - len(p)。我们只要针对这些字符，加上对应的字符使他们在新的字符串s'当中有对称的字符，这就是我们最少要额外加上的字符。比如对于字符串"adbcdxbd"当中，我们能找到的最长回文子序列为"dbcbd"，那么剩下的字符我们插入对应的对称字符，我们可以得到"adb(xd)cdxbd(a)"。括号内为新插入的字符。至于为什么这个一定是插入最少的，因为我们找的是最长的回文子序列。剩下的那些字符，无论如何我们都是要插入字符和其match的。所以这道题其实就等价于找最长回文子序列，参考这篇文章。时间复杂度O(n^2)，空间复杂度可以用滚动数组优化到O(n)，代码如下：

	//POJ 1159
	//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.
	#include<iostream>
	#include<algorithm>
	#include<stdlib.h>
	#include<stdio.h>
	#include<iomanip>
	#include<string.h>
	using namespace std;
	const int MAX=5005;
	int len;
	char s1[MAX];
	char s2[MAX];
	int dp[2][MAX];//will MLE if not intialize as short array
	int LCS(char* s1, char* s2, int len)
	{
	int e = 1;
	for(int i = 0; i < len; ++i, e ^= 1)
	{
	for(int j = 0; j < len; ++j)
	{
	dp[e][j + 1] = s1[i] == s2[j]? dp[e ^ 1][j] + 1: max(dp[e ^ 1][j + 1], dp[e][j]);
	}
	}
	return dp[e ^ 1][len];
	}
	int main()
	{
	cin.sync_with_stdio(false);
	while (cin >> len)
	{
	cin >> s1;
	for(int i = 0; i < len; ++i)
	s2[len - 1 - i] = s1[i];
	memset(dp, 0, sizeof(dp[0][0]) * MAX);
	//let s' be reverse s
	//answer = len - LongestCommonSubstring(s, s')
	cout << len - LCS(s1, s2, len) << endl;
	}
	return 0;
	}

view raw POJ_1159_Palindrome_LCS.cpp hosted with ❤ by GitHub