题目
P1435 [IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入格式
共一行，包含一个由大写字母ABCD构成的字符串，表示现在看到的密码串。
输出格式
输出一个整数，表示至少脱落了多少个种子。
数据范围
输入字符串长度不超过1000
输入样例1：
ABCBA
输出样例1：
0
输入样例2：
ABDCDCBABC
输出样例2：
3
解题
方法一：DFS(递归)(超时)
思路
对于给定的字符串可以从两边开始比对，讨论需要恢复多少个字符能达到镜像的效果。
如果左右镜像位置的字符相同则不需要恢复字符，但是如果不同就需要讨论恢复左边字符还是恢复右边字符。
那么就可以使用递归方式求解：
- 维护两个指针分别指向字符串两端。
- 如果左右两边指向的字符相同，则递归两个指针都向中间推进一位的情况。
- 否则分别递归左指针推进一位(模拟在右侧补了一位字符)和右指针推进一位(模拟在左侧补了一位字符)的情况，取较小的脱落数返回。
- 递归的结束条件是：左右指针相撞。
- 剪枝的条件是：当前脱落数已经大于维护的最小脱落数。
如图是当输入字符串为 ABDCDCBABC 时反推出的所有原字符串的可能：
时间复杂度：。
在题目给定 1000 的数据范围下会超时。
代码
import java.util.*;
import java.io.*;
public class Main {
static char[] chs;
static int minCnt = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
chs = in.readLine().toCharArray();
System.out.println(dfs(0, chs.length - 1, 0));
}
static int dfs(int left, int right, int cnt) {
if (cnt >= minCnt) return minCnt;
if (left >= right) {
if (cnt < minCnt) minCnt = cnt;
return cnt;
}
if (chs[left] == chs[right]) return dfs(left + 1, right - 1, cnt);
else return Math.min(dfs(left + 1, right, cnt + 1), dfs(left, right - 1, cnt + 1));
}
}
方法二：动态规划
思路
要求原字符串是左右对称的，也就是回文串，那么可以把原串翻转一下，原串与翻转串能匹配上的子序列就是原来就有的回文字符，这样的话原串长度减去该子序列的长度就是脱落的种子数。需要脱落的种子数尽量少，那么原有的回文字符就应该尽量多，也就是应该求原串与翻转串的 LCS (最长公共子序列)。
LCS 问题是经典的动态规划题，详见：【动态规划, LCS】最长公共子序列
代码
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String str = in.readLine();
String revStr = new StringBuilder(str).reverse().toString();
System.out.println(str.length() - lcs(str, revStr));
}
static int lcs(String str1, String str2) {
int m = str1.length(), n = str2.length();
char[] chs1 = str1.toCharArray(), chs2 = str2.toCharArray();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
char c1 = chs1[i - 1];
for (int j = 1; j <= n; ++j) {
char c2 = chs2[j - 1];
if (c1 == c2) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
}
评论区