@toc

1、题目描述

X 星球的考古学家发现了一批古代留下来的密码。

这些密码是由 A、B、C、D 四种植物的种子串成的序列。

仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。

由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入描述

输入一行，表示现在看到的密码串（长度不大于 1000）。

输出描述

要求输出一个正整数，表示至少脱落了多少个种子。

输入输出样例

输入1

ABCBA

输出1

0

输入2

ABDCDCBABC

输出2

3

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

2、思路分析

2.1 思路一：双指针法(并没有完全通过所有用例)

这种思路虽然没有通过全部用例，但我感觉这个思想不错，还是写出来，这个思想来源于B站：https://www.bilibili.com/video/BV1jy4y117n7/?spm_id_from=333.1007

题目中问的是脱落了几个种子，也就是说从原来的回文串到现在剩下的串是少了几个字符变过来的。我们反过来想，其实就是问我们现在剩的这个字符串插入几个字符能够补回到原来的回文串。

我们原来判断回文串的用的双指针，用两个左、右指针逐步判断就行，当 $s[left]==s[right]$时，左指针往右边走，右指针往左边走，当 $left\ge right$的时候证明这个字符串是个回文串。

我们现在依然使用双指针，逐个判断字符是否相等，当 $s[left]==s[right]$的时候，我们继续往下走，当 $s[left]\ne [right]$的时候，我们分两步，

• 第一步是left不动，让right不断左移，直到 $s[left]==s[right]$的时候停下，用一个变量统计移动的次数count1
• 第二步是right不动，让left不断向右移动，直到 $s[left]==s[right]$的时候停下，同样用比那辆统计移动的次数count2

其实上面两步最差的情况是left右移到right，right左移到left，

上面移动的过程需要另外使用两个工作指针实现(可以看作游标)。

我们取count1和count2的最小值， $min(count1,count2)$,这个计数其实就是我们往字符串中需要插入多少个字符，才能保证当前的这个子串是个回文，然后每次移动结束之后用一个变量count+=min(count1,count2)即可。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) throws IOException {
        String str = nextString();
        long count = findCode(str);
        System.out.println(count);
    }
    //查找对称序列需要添加的符号数量
    public static long findCode(String code){
        char[] codeChars = code.toCharArray();
        long count=0;   //计算得到的符号数量，最终返回该值
        int left=0;
        int right=codeChars.length-1;
        int leftCount=0;    //
        int rightCount=0;
        while(left<right){
            if(codeChars[left]==codeChars[right]){//相等 继续往前走
                left++;
                right--;
                continue;
            }
            leftCount=0;
            int leftCursor=left; //左工作指针，因为left是不能动的，我们使用这个游标取寻找
            while(codeChars[leftCursor]!=codeChars[right]){
                leftCursor++;   //继续向右边走
                leftCount++;    //左边要添加的字符数累加
            }
            rightCount=0;
            int rightCursor=right;  //右工作指针
            while(codeChars[rightCursor]!=codeChars[left]){
                rightCursor--;  //继续向左边走
                rightCount++;
            }
            //取最近的
            if(leftCount<rightCount){   //左边走的步数少
                left+=leftCount;    //从左往右走
            }else{  //右边走的步数少
                right-=rightCount; //从右往左走
            }
            count+=Math.min(leftCount,rightCount);
        }
        return count;
    }
    public static String nextString() throws IOException{
        st.nextToken();
        return st.sval;
    }
}

这种代码并不能通过所有的用例，原因暂时还不清楚，但是我感觉这个思路非常清晰，值得一观。

2.2 思路二：最大公共子串问题(AC)

我们只需要在现在的字符串中找到最长回文子串，剩下的字符个数就等于已经脱落的字符个数，那么我们怎么求当前字符串的最大回文子串呢？

我们的目的是统计出不在最长回文子串中的字符个数。将字符串逆置，找原来串和逆置后的串的最长公共子序列，这个最长公共子序列一定是回文，且

$字符串的长度-最长公共子序列的长度=最小掉落的种子$

我们用dp[i][j]表示a[0:i]和b[0:j]的最长公共子序列的长度。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * 求字符串中有几个单泵字符，在现在的字符串中，找那个最长回文子串，
 * 不在最长回文子串中的字符就是单泵字符。
 * 将字符串逆置，找两个串的最长公共子序列，这个最长的公共子序列一定是回文，
 * 且字符串的长度-最长公共子序列的长度=最小掉落的种子
 * dp[i][j]表示a[0:i]和b[0:j]的最长公共子序列的长度
 * dp[0][j]=0,dp[i][0]=0
 */
public class Main1 {
    public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) throws IOException {
        String str = nextString();
        String str1 = new StringBuffer(str).reverse().toString();
//        System.out.println(str);
//        System.out.println(str1);
        char[] c1 = str.toCharArray();
        char[] c2 = str1.toCharArray();
        int n=str.length();
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <=n; i++) {
            for (int j = 1; j <=n ; j++) {
                if(c1[i-1]==c2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        //求出最长公共子序列的长度
        int len = dp[n][n];
        //最小调用的种子=字符串长度-最长公共子序列的长度
        int min = str.length() - len;
        System.out.println(min);
    }

    public static String nextString() throws IOException{
        st.nextToken();
        return st.sval;
    }
}

快1点了，有点困了，上面的思路可能在细节方面有点欠缺，以后补上吧。