首页 > 试题广场 >

构造回文

[编程题]构造回文
  • 热度指数:36597 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢?
输出需要删除的字符个数。

输入描述:

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



输出描述:

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

示例1

输入

abcda
google

输出

2
2
#Python版 
#思路:最长会文字序列:==  Str与reverse_Str的最长公共字序列
#注意:碰到了楼上Python解法同样的问题,没把循环过程放到name中,一直说是过90% 
#然后超时,放进去就好了。猜一下:是不是给了程序入口能加快解析  # -*- coding:utf-8 -*-
import sys


def maxlcp(strs):
    if strs==None or len(strs)==0:
        return 0
    lens = len(strs)
    dp =[0] *lens
    dp[0] = 1 if strs[0] == strs[lens-1] else 0
    for i in range(lens):
        pre = dp[0]
        dp[0] = max(dp[0],1 if strs[i] == strs[lens-1] else 0)
        for j in range(1,lens):
            cur = dp[j]
            dp[j] = max(dp[j],dp[j-1])
            if strs[i] == strs[lens-1-j]:
                dp[j] = max(dp[j],pre+1)
            pre = cur

    return dp[lens-1]


if __name__ == '__main__':
    while True:
        line = sys.stdin.readline().strip()
        lens = len(line)
        if not line:
            break
        maxLcp = maxlcp(line)
        # print lens
        # print maxLcp
        print lens - maxLcp


发表于 2017-02-25 09:43:32 回复(5)
大家都在用最大子序列解这道题,我想了一个适用于这道题的动态规划,感觉比lcs快
用python写的,总说我超时
然后我就实现了lcs版本的,依旧超时,我终于明白
锅在python!锅在python!锅在python!!!
这种限定死时间空间的题,对所有语言采用相同的标准太不公平了,笔试的时候一定不能选python,吃大亏
最后我实现了c++的版本
include<iostream>
#include<string>

using namespace std;
const int MAX_LENGTH = 1002;
int dynamic[MAX_LENGTH][MAX_LENGTH];

int min_palindrome(string s)
{
  if(s.length() <= 1)
    return 0;
  for(int i=0; i<s.length(); ++i)
  {
    dynamic[i][i] = 0;
  }
  for(int l=2; l<=s.length(); ++l)
  {
    for(int s_ind=0; s_ind<=s.length()-l; ++s_ind)
    {
      if(s[s_ind] == s[s_ind+l-1])
        dynamic[s_ind][s_ind+l-1] = s_ind+1<=s_ind+l-2 ? dynamic[s_ind+1][s_ind+l-2] : 0;
      else
        dynamic[s_ind][s_ind+l-1] = 1 + min(dynamic[s_ind+1][s_ind+l-1], dynamic[s_ind][s_ind+l-2]);
    }
  }
  return dynamic[0][s.length()-1];
}

int main()
{
  string s;
  while(cin >> s)
  {
    cout << min_palindrome(s) << endl;
  }
}
python 版本,只能通过90%
import sys
def min_palindrome(s):
    if len(s) <= 1:
        return 0
    dynamic = [[0] * len(s)] * len(s)
    for l in xrange(2, len(s)+1):
        for s_ind in xrange(0, len(s)+1-l):
            if s[s_ind] == s[s_ind + l-1]:
                dynamic[s_ind][s_ind + l-1] = 0 if s_ind+1>s_ind + l-2 else dynamic[s_ind+1][s_ind + l-2]
            else:
                dynamic[s_ind][s_ind + l-1] = 1 + min(dynamic[s_ind+1][s_ind + l-1], dynamic[s_ind][s_ind + l-2])
    return dynamic[0][len(s)-1]
for line in sys.stdin:
    print min_palindrome(line.strip())

发表于 2017-08-24 20:00:58 回复(3)
import java.util.Scanner;
public class ConstructPlalindrome { public static void main(String[] args) { Scanner scan = new Scanner(System.in); while(scan.hasNext()) { String s = scan.nextLine(); System.out.println(s); int len = lenghOfLCS(s, new StringBuffer(s).reverse().toString()); System.out.println(s.length() - len); } scan.close(); } //动态规划求最长公共子序列的长度 public static int lenghOfLCS(String s1, String s2) { char[] ch1 = s1.toCharArray(); char[] ch2 = s2.toCharArray(); int n1 = s1.length(); int n2 = s2.length(); int[][] table = new int[n1][n2];//所有元素默认初始化为0 if(ch1[0] == ch2[0]) table[0][0] = 1; //单独计算s2与s1首字母之间的的LCS长度 for(int i = 1; i < n2; ++i) { if(ch1[0] == ch2[i]) table[0][i] = 1; else table[0][i] = table[0][i-1]; } //单独计算s1与s2首字母之间的LCS长度 for(int i = 1; i < n1; ++i) { if(ch2[0] == ch1[i]) table[i][0] = 1; else table[i][0] = table[i-1][0]; } //递推求解各个字符处的LCS for(int i = 1; i < n1; ++i) { for(int j = 1; j < n2; ++j) { if(ch1[i] == ch2[j]) { table[i][j] = table[i-1][j-1] + 1; }else table[i][j] = table[i-1][j] > table[i][j-1] ? table[i-1][j] : table[i][j-1]; } } return table[n1-1][n2-1]; } }

动态规划求解最长公共子序列(LCS)
编辑于 2016-06-27 15:45:58 回复(3)
为什么都用最长公共子串来做,最长回文子序列不可以吗?
#include<iostream>
#include<math.h>
#include<string>
#include<algorithm>
using namespace std;
int solve(string str){
    int n=str.size();
    int *flag=new int[n*n];
    for(int i=0;i<n*n;i++){
        flag[i]=0;
    }
    for(int i=n-1;i>=0;i--){
        flag[i*n+i]=1;
        for(int j=i+1;j<n;j++){
            if(str[i]==str[j])
                flag[i*n+j]=flag[(i+1)*n+j-1]+2;
            else
                flag[i*n+j]=max(flag[(i+1)*n+j],flag[i*n+j-1]);
        }
    }
    int res=n-flag[n-1];
    return res;
}
int main(){
    string s;
    while(cin>>s){
        cout<<solve(s)<<endl;
    }
    return 0;
}

编辑于 2016-08-16 10:23:02 回复(2)
不要用递归做!不要用递归做!不要用递归做!重要的事情说三遍,懒得想动态规划,直接递归果然超时了。。。。。。
发表于 2016-07-24 23:33:09 回复(3)
#include<iostream>
#include<string>
using namespace std;
int main(){
    string s1;
    int max_len[1001][1001];
    while(cin >> s1){
        string s2(s1.rbegin(), s1.rend());
        for(int i=0;i<=s1.length();i++)
            for(int j=0;j<=s2.length();j++){
                if(i==0 || j==0 )
                    max_len[i][j] = 0;
                else if(s1[i-1] == s2[j-1])
                    max_len[i][j] = max_len[i-1][j-1] + 1;
                else
                    max_len[i][j] = max(max_len[i-1][j] , max_len[i][j-1]);
            }
        cout << s1.length() - max_len[s1.length()][s2.length()] <<endl;
    }   
}

发表于 2017-05-28 19:27:16 回复(0)
    果然还是动态规划来解释比较简单的了。。。之前自个理解错了。。很僵硬
基于JavaScript使用动态规划的代码:
function Max(a,b){
	return a>b?a:b;
}
function find (str1) {
	var str2 = str1.split("");str2 = str2.reverse();str2 = str2.join("");
	var max = 0;
	var resArr = new Array(str1.length+1);
	for(var i = 0;i<=str1.length+1;i++){  //初始化
		resArr[i] = new Array(str2.length+1);
		for(var j = 0;j<=str2.length+1;j++){
			resArr[i][j] = 0;
		}
	}

	for(var i = 0;i<=str1.length;i++){
		for(var j = 0;j<=str2.length;j++){
			if(i==0||j==0){
				resArr[i][j] = 0;
			}else{
				if(str1[i-1] == str2[j-1]){
					resArr[i][j] = resArr[i-1][j-1]+1;//前一次循环中数组元素保存的值加1
				}else{
					resArr[i][j] = Max(resArr[i-1][j],resArr[i][j-1]);//不用连续
				}
			}
			if(max<resArr[i][j]){
				max = resArr[i][j];//保存最大的数,也就是匹配最长的长度
			}
		}
	}
	//输出结果
	if(max == 0){
		return str1.length;
	}else{
		return str1.length-max;
	}
}
再贴一个不基于动态规划的解法:
    把输入的字符串按照中间夹杂的杂项数量分为三种情况:
        1.回文之间杂项为0。例如:abccba(0)、abba(0)、google(2)这种。
        2.回文之间杂项为1。例如:   goXogle(2)、abXba(0)这种。
        3.回文之间杂项大于1。例如:abcda(2)、goabcogle(4)这种。
    然后对应每种情况来解:
function getCount(str){
    var strArr = str.split("");
    var strLen = 0;
    for(var i=0;i<strArr.length;i++){
        for(var j=strArr.length;j>=i;j--){
            if(strArr[i]==strArr[j]){
                var count = 1;
                var temp_i = i,temp_j = j;
                while(strArr[++temp_i]==strArr[--temp_j]){
                    if(temp_i<temp_j){//情况一
                    	count++;
                    }else if(temp_i == temp_j){//情况二
                    	count+=0.5;
                    }else{//防止死循环
                    	break;
                    }
                }
                if(temp_j>temp_i){//情况三
                	count+=0.5;
                }
               if(count>strLen){
                   strLen = count;
               }
            }
        }
    }
    return str.length-Math.floor(strLen*2);
}

发表于 2017-04-04 11:13:10 回复(1)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String str =sc.nextLine();
            char[] strchar = str.toCharArray();
            int length= strchar.length;
            int[][] dp = new int[length][length];
            for(int j=1;j<length;j++){
                dp[j-1][j]=strchar[j-1]==strchar[j]?0:1;
                for(int i=j-2;i>-1;i--){
                    if(strchar[i]==strchar[j]){
                        dp[i][j]=dp[i+1][j-1];
                    }else{
                        dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;
                    }
                }
            }
        }
    }
}


发表于 2016-06-12 23:10:44 回复(7)
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
 
 
//自底向顶的动态规划
intLCS(string str1, string str2, intn1, intn2)
{
    vector<vector<int>> nVec(n1+1);
    for(inti = 0; i < n1+1; ++i)
    {
        nVec[i].assign(n2+1, -1);
    }
    for(inti = 0; i < n2+1;++i)
    {
        nVec[0][i] = 0;
 
    }  
    for(inti = 0; i < n1+1; ++i)
    {
        nVec[i][0] = 0;
    }
    for(inti = 1; i <= n1;++i)
    {
        for(intj = 1; j <= n2;++j)
        {
            if(str1[i-1] == str2[j-1])
            {
                nVec[i][j] = nVec[i - 1][j - 1] + 1;
 
            }
            else
            {
                nVec[i][j] = max(nVec[i][j - 1], nVec[i - 1][j]);
            }
        }
    }
    returnnVec[n1][n2];
}
intmain()
{
    string str;
    while(cin>>str){
        string::size_type nLen = str.size();
        string str1 = str;
        reverse(str1.begin(),str1.end());
        cout<<nLen - LCS(str,str1,nLen,nLen)<<endl;
    }
    return0;
}
发表于 2016-05-17 19:05:42 回复(4)

pyhon使用DP的解决方案

import sys
def main():
    for line in sys.stdin:
        str1 = line[:-2]
        n = len(str1)
        str2 = str1[::-1]
        rec = [[0 for x in range(n+1)] for x in range(n+1)]
    for i in range(1,n+1):
            for j in range(1,n+1):
            if str1[j-1] == str2[i-1]:
                    rec[i][j] = rec[i-1][j-1] + 1
                else:
                    rec[i][j] = max(rec[i-1][j], rec[i][j-1])
    print n - rec[n][n]
main()
编辑于 2018-04-03 17:49:54 回复(1)
提到回文串,自然要利用回文串的特点,想到将源字符串逆转后,“回文串”(不一定连续)相当于顺序没变
求原字符串和其反串的最大公共子序列(不是子串,因为可以不连续)的长度(使用动态规划很容易求得),然后用原字符串的长度减去这个最大公共子串的长度就得到了最小编辑长度。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int MAX = 1001;
int MaxLen[MAX][MAX]; //最长公共子序列,动态规划求法
int maxLen(string s1, string s2){
	int length1 = s1.size();
	int length2 = s2.size();
	for (int i = 0; i < length1; ++i)
		MaxLen[i][0] = 0;
	for (int i = 0; i < length2; ++i)
		MaxLen[0][i] = 0;
	
	for (int i = 1; i <= length1; ++i)
	{
		for (int j = 1; j <= length2; ++j)
		{
			if (s1[i-1] == s2[j-1]){
				MaxLen[i][j] = MaxLen[i-1][j - 1] + 1;
			}
			else
			{
				MaxLen[i][j] = max(MaxLen[i - 1][j], MaxLen[i][j - 1]);
			}
		}
	}

	return MaxLen[length1][length2];
}

int main(){
	string s;
	while (cin >> s){
		int length = s.size();
		if (length == 1){
			cout << 1 << endl;
			continue;
		}
		//利用回文串的特点
		string s2 = s;
		reverse(s2.begin(),s2.end());
		int max_length = maxLen(s, s2);
		cout << length - max_length << endl;
	}
	return 0;
}

编辑于 2016-09-18 07:56:00 回复(15)

C++ 动态规划

#include <bits/stdc++.h>

using namespace std;

/*
dp[i][j]: i到j的最长回文子序列长度
1. s[i] = s[j], 则dp[i][j] = dp[i + 1][j - 1] + 2;
2. s[i] != s[j], dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
边界: dp[i][i] = 1;
*/
int main() {
    string s;
    int dp[1003][1003];
    while (cin >> s) {
        int n = s.size();
        for (int i = 0; i < n; ++i) dp[i][i] = 1;
        for (int j = 1; j < n; ++j) {
            for (int i = j - 1; i >= 0; --i) {
                if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
            }
        }
        cout << n - dp[0][n - 1] << endl;
    }
    return 0;
}
发表于 2022-08-20 11:37:25 回复(0)
动态规划求解
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1;
        // 最长回文串的长度其实就是原串及其反转串的最长公共子串的长度(无需连续),原串长度减去这个长度就是要删除的字符数
        while((str1 = br.readLine()) != null) {
            String str2 = new StringBuilder(str1).reverse().toString();
            int n = str1.length();
            int[][] dp = new int[n + 1][n + 1];
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++)
                    dp[i][j] = str1.charAt(i - 1) == str2.charAt(j - 1)? dp[i - 1][j - 1] + 1: Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
            System.out.println(n - dp[n][n]);
        }
    }
}


发表于 2021-02-08 15:32:28 回复(0)
public static int maxLen(String str) {
    StringBuilder sb1 = new StringBuilder(str);
    StringBuilder sb2 = new StringBuilder(str).reverse();
    int len = str.length();
    int[][] maxLen = new int[len + 1][len + 1];
    for (int i = 1; i <= len; i++) {
        for (int j = 1; j <= len; j++) {
            if (sb1.charAt(i - 1) == sb2.charAt(j - 1))
                maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
            else
                maxLen[i][j] = Math.max(maxLen[i - 1][j], maxLen[i][j - 1]);

        }
    }
    return len - maxLen[len][len];
}


发表于 2019-08-12 10:22:35 回复(0)

开始用了递归,时间复杂度太高,改用了动态规划,通过。

/* 做题需要脑子,多分析思考。。
 * 多思考,问题会很简单。。。。
 * 数学分析。。。。。。。。。。 
 */
#include<stdio.h>
char s[1000];
int a[1000][1000];

int min( int x, int y)
{
    return x<y?x:y;
} 

//递归时间复杂度太高了,改用动态规划 
int func( int begin, int end)
{
    int i, k;
    for( k=1; k<end-begin+1; k++)
    {
        for( i=begin; i<end; i++)
        {
            if( s[i]==s[i+k]) a[i][i+k]=a[i+1][i+k-1];
            else a[i][i+k] = min( a[i][i+k-1], a[i+1][i+k])+1;
        }
    }
    return a[begin][end];
}

int main()
{
    int i=0, j, flag=0; char c;

    while(1)
    {
        for( i=0; (c=getchar())!=EOF; i++)
        {
            if( c=='\n') break;
            s[i]=c;
        }
        if( c==EOF) break;
        printf( "%d\n", func( 0, i-1));
    }

    return 0;
}
发表于 2018-04-05 13:42:50 回复(0)
我TM只想说好坑啊,腾讯的输入得用cin >> s而不能用getline(cin, s),用getline末尾会多出空格……
发表于 2018-04-05 08:31:17 回复(0)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int solution(string s){
    int result;
        int n=s.length();
        int dp[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dp[i][j]=0;
            }
        }
        for(int j=0;j<n;j++){
            dp[j][j]=1;
        }
        for(int j=1;j<n;j++){
            for(int k=0;k<n-j;k++){
                if(s[k]==s[k+j]){
                     dp[k][k+j]=dp[k+1][k+j-1]+2;
                }
                else{
                     dp[k][k+j]=max(dp[k+1][k+j],dp[k][k+j-1]);
                }
            }
        }
        result=n-dp[0][n-1];
    return result;
}
int main(){
    string s;
    while(cin>>s){
        cout<<solution(s)<<endl;
    }
    return 0;
}
编辑于 2017-07-10 18:26:03 回复(0)
求大大大看看,我这怎么怎么不对啊!!只能过40%a1
和标准答案的区别是求最大公共子串长时,他们遍历的是各个字串长度,我遍历的各个字串位置!
#include<bits/stdc++.h>
using namespace std;

int getGGZC(string s1,string s2){
vector<vector<int>> ss(s1.size(),vector<int>(s2.size(),0));


//初始化 如s1="abc" s2="acdeeee"。s1和s2首字母相等则
//ss[0][0](a,a),ss[0][1](a,ac),ss[0][2](a,acd)...
//ss[1][0](a,a),ss[2][0](ab,,a),ss[3][0](abc,a)...等最长公共子串都是1.
//首字母不等则都为0.
if(s1[0]==s2[0]){
for(int i=0;i<s1.size();i++){
ss[i][0]=1;
}
for(int j=0;j<s2.size();j++){
ss[0][j]=1;
}
}


//i,j分别表示s1和s2上字符的位置
//如 s1="abc" s2="acdeeee" ss[1][2]的值就是“ab”和“acd”的最大公共子串长
for(int i=1;i<s1.size();i++){
for(int j=1;j<s2.size();j++){
if(s1[i]==s2[j])ss[i][j]=ss[i-1][j-1]+1;
else{
ss[i][j]=max(ss[i-1][j],ss[i][j-1]);
}
}
}
int a=ss[s1.size()-1][s2.size()-1];

return a;

}


int main(){
string str;
while(cin>>str){

string ss=str;
reverse(ss.begin(),ss.end());

cout<<ss.size()-getGGZC(str,ss)<<endl;
}

return 0;
}

编辑于 2017-06-09 15:22:02 回复(2)
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
intmain(){
     
    string str;
    while(cin >> str){
        string s1(str);
        string s2(str.rbegin(),str.rend());
        intlen = s1.size();
        vector< vector<int> >lcs(len+1,vector<int>(len+1,0));
       /*
        for(int i = 0; i < len+1;++i){
            lcs.at(i).at(0) = 0;
        }
        for(int i = 0; i < len+1; ++i){
            lcs.at(0).at(i) = 0;
        }
        */
        for(inti = 1; i <= len; ++i){
            for(intj = 1; j <= len; ++j){
                if(s1.at(i-1) == s2.at(j-1)){
                    lcs.at(i).at(j) = lcs.at(i-1).at(j-1) + 1;
                }
                else{
                    lcs.at(i).at(j) = max(lcs.at(i).at(j-1), lcs.at(i-1).at(j));
                }
                 
            }  
        }
         
       
        cout<< len - lcs.at(len ).at(len)<<endl;
         
         
    }
     
     
    return0;
发表于 2017-04-01 15:42:53 回复(0)
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)

问题信息

难度:
168条回答 52265浏览

热门推荐

通过挑战的用户