我要招人

去企业版

首页 > 试题广场 >

构造回文

[编程题]构造回文

热度指数：36641 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。

输入描述:


输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:

对于每组数据，输出一个整数，代表最少需要删除的字符个数。

示例1

输入

abcda
google

输出

2
2

算法知识视频讲解

查看答案及解析

Java

谭博-好好学习

//想了几天，总算学了个皮毛：
//时间 O(n2)    空间  O(n2)

import java.util.Scanner;

public class Main {
//public class NowCoder1 {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        while (s.hasNext()) {
            String origin = s.next();
            int ans = getMaxLen(origin);
            System.out.println(ans);
        }
        s.close();


    }

    private static int getMaxLen(String origin) {
        //此题跟leetcode求最长回文字串，类似。
        int len = origin.length();

        int reLen;

        int[][] dp = new int[len][len];


        //这段要的，跟leetcode不一样。这里计算长度要算是单个字符。
        //如果 是 aba，这里的长度要加入b计算，如果是aa，那么就不会用到dp[i][i]
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }

        //注意这里 从 i=j-1 开始，因为忽略非回文并计算长度，填图顺序与leetcode 那题不一样。
        for (int j = 1; j < len; j++) {
            for (int i = j - 1; i >= 0; i--) {
                if (origin.charAt(i) == origin.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }

        //长度值，在这种顺序填写下，向右上角逐渐合并，所以取 dp[0][len - 1]
        reLen = dp[0][len - 1];
        return len - reLen;
    }


}

发表于 2020-06-18 13:03:38 回复(0)

Java

我真TM没开挂

面向对象的语言和面向过程的语言限定相同的时间没有可比性，看了一遍基本没有用递归做的java，附上dp迭代的代码

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

public class DeletePalindrome {
    public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int len = line.length();
            int[][] nums = new int[len][len];
            char[] line_1 = new char[len];
            char[] line_2 = new char[len];
            for (int i = 0; i < len; i++) {
                line_1[i] = line.charAt(i);
                line_2[i] = line.charAt(len - 1 - i);
            }

            int i = 0;
            while (i < len) {
                if (line_1[0] != line_2[i]) {
                    nums[i][0] = 0;
                } else {
                    while (i < len) {
                        nums[i][0] = 1;
                        i++;
                    }
                    break;
                }
                i++;
            }
            i = 0;
            while (i < len) {
                if (line_2[0] != line_1[i]) {
                    nums[0][i] = 0;

                } else {
                    while (i < len) {
                        nums[0][i] = 1;
                        i++;
                    }
                    break;
                }
                i++;
            }
            for (int i_index = 1; i_index < len; i_index++) {
                for (int j_index = 1; j_index < len; j_index++) {
                    if (line_1[j_index] == line_2[i_index]) {
                        nums[i_index][j_index] = nums[i_index - 1][j_index - 1] + 1;
                    } else {
                        nums[i_index][j_index] = Math.max(nums[i_index][j_index - 1], nums[i_index - 1][j_index]);
                    }
                }
            }
            System.out.println(len - nums[len - 1][len - 1]);
        }
    }    
}

编辑于 2019-04-22 10:42:15 回复(0)

Java

AllenHua

【动态规划】最长公共子序列与最长公共子串

http://www.cnblogs.com/en-heng/p/3963803.html

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            String str = scan.nextLine();
            String reverseStr = new StringBuilder(str).reverse().toString();
            System.out.println(str.length() - lcs(str, reverseStr));
        }
    }
    // 求最长公共子串长度 Longest Common Subsequence LCS算法
    private static int lcs(String str, String reverseStr) {
        // TODO Auto-generated method stub
        int len1 = str.length();
        int len2 = reverseStr.length();
        int result = 0;// 记录下最长公共子串长度
        int[][] c = new int[len1 + 1][len2 + 1];        
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (str.charAt(i) == reverseStr.charAt(j)) {
                    c[i + 1][j + 1] = c[i][j] + 1;
                } else {
                    c[i + 1][j + 1] = Math.max(c[i][j + 1], c[i + 1][j]);
                }
            }
        }
        return c[len1][len2];
    }
}

编辑于 2018-05-14 14:40:06 回复(0)

Java

夜临永寂

import java.util.*;
public class Main{
    public static void main(String[] arg){
        Scanner input = new Scanner(System.in);
        while(input.hasNextLine()){
            String s = input.nextLine();
            char[] c = s.toCharArray();
            intlen  = c.length;
            int[][] state = new int[len+1][len+1];
            state[0][0] = 0;
            for(int i = 0; i < len; i++){   //正序的每一个字符同反序的每一个字符比较
                for(int j = 0; j < len; j++){
                    if(c[i] == c[len-1-j]) state[i+1][j+1] = state[i][j] + 1;  //字符是相同的  则前一个字符相同的数加一
                    else state[i+1][j+1] = Math.max(state[i+1][j],state[i][j+1]); //对应的字符不相同  则取前面相同字符数中最大那个
                    //这样得到就是相同字符数最多的值  就是回文的长度  总长减去此长  就得到要删减的数目
                }
            }
            System.out.println(len - state[len][len]);
        }
    }
}

编辑于 2017-03-19 21:07:42 回复(0)

Java

詆調壹點

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String s1 = sc.next();
			String s2 = new StringBuilder(s1).reverse().toString();
			int[][] dp = new int[s1.length() + 1][s2.length() + 1];
			for (int i = 1; i < dp.length; i ++ ) {
				for (int j = 1; j < dp[0].length; j ++ ) {
					dp[i][j] = s1.charAt(i - 1) == s2.charAt(j - 1) ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
			System.out.println(s1.length() - dp[s1.length()][s2.length()]);
		}
	}
}

发表于 2016-12-02 22:37:07 回复(10)

Java

Gavin_ZYX

//已验证

import java.util.Scanner;

public class Main{

public static void main(String [] args) {

Scanner in = new Scanner(System.in);

while (in.hasNextLine()) {//注意while处理多个case

String str =in.nextLine();

int i = deleteLength(str);

System.out.println(i);

}

private static int deleteLength(String str) {

int length = str.length();

char [] chars = str.toCharArray();

int [][] lcs = new int[length + 1][length + 1];

for(int i = 0; i<length; i++) {

for(int j = 0; j<length; j ++) {

if(chars[i] == chars[length - j - 1]) {

lcs[i + 1][j + 1] = lcs[i][j] + 1;

} else {

int max = lcs[i][j + 1] > lcs[i + 1][j]?lcs[i][j + 1]:lcs[i + 1][j];

lcs[i + 1][j + 1] = max;

}

return length - lcs[length][length];

}

发表于 2016-10-20 16:44:11 回复(0)

Java

leiyesky

import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			String str = in.nextLine();
			System.out.println(L(str));
		}
	}
	
	public static int L(String str){
		
		String strL = new StringBuffer(str).reverse().toString();//字符串反转
		int len = str.length();
		int map[][] = new int[len+1][len+1];
		for(int i=0;i<len;i++){
			for(int j=0;j<len;j++){
				map[i][j] = 0;
			}
		}
		for(int i=0;i<len;i++){
			for(int j=0;j<len;j++){
				if(str.charAt(i)==strL.charAt(j)){
					map[i+1][j+1] = map[i][j]+1;
				}else{
					map[i+1][j+1] = Math.max(map[i][j+1], map[i+1][j]);
				}
			}
		}
		return len-map[len][len];//map[len][len]保存的是最大公共子串的长度
	}

}

发表于 2016-08-03 17:14:05 回复(2)