首页 > 试题广场 >

回文字符串

[编程题]回文字符串
  • 热度指数：9366 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
最大回文子串是被研究得比较多的一个经典问题。最近月神想到了一个变种，对于一个字符串，如果不要求子串连续，那么一个字符串的最大回文子串的最大长度是多少呢。

数据范围：字符串长度满足 ，字符串中仅包含 0~9 和大小写字母

输入描述:
每个测试用例输入一行字符串（由数字0-9，字母a-z、A-Z构成），字条串长度大于0且不大于1000.


输出描述:
输出该字符串的最长回文子串的长度。（不要求输出最长回文串，并且子串不要求连续）
示例1

输入

adbca

输出

3

说明

因为在本题中，不要求回文子串连续，故最长回文子串为aba(或ada、aca)

备注:
因为不要求子串连续，所以字符串abc的子串有a、b、c、ab、ac、bc、abc7个
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int n = s.length();
    int dp[n][n];
    memset(dp,0,sizeof(dp));
    for(int j=0;j<n;j++){
        dp[j][j] = 1;
        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+1][j], dp[i][j-1]);
        }
    }
    cout<<dp[0][n-1]<<endl;

    return 0;
}

发表于 2019-07-14 22:40:04 回复(0)
更多回答
qianjiahong头像 qianjiahong 
#include <iostream>
#include<bits/stdc++.h>
#define N 1000
using namespace std;
//可以使用递归的算法，但是这种算法对于字符串较大的情况会通不过，但是思路很简单
int dp(char*s,int start, int end){
    if (start>end){
        return 0;
    }else if(start==end){
        return 1;
    }else{
        if(s[start]==s[end]){
            return dp(s,start+1,end-1)+2;
        }else{
            return max(dp(s,start+1,end),dp(s,start,end-1));
        }
    }
}

//使用动态规划的思想，d[i][j]表示字符串s中位置j到位置i（i>j）的字符串中的最长的回文长度，
//当s[i]==s[j]时,d[i][j]的最长回文字符串长度为其子串d[i-1][j+1]的长度+2
//当s[i]!=s[j]时,d[i][j]的最长回文字符串长度为d[i-1][j]和d[i][j+1]两个中的最大值
//最后，d[n-1][0]就是最后的长度
int dp(char*s){
    int n =strlen(s);
    int i,j;
    int d[N][N];
    for(i=0;i<n;i++){
        d[i][i]=1;
        for(j=i-1;j>-1;j--){
            if(s[i]==s[j]){
                d[i][j]=d[i-1][j+1]+2;
            }else{
                d[i][j]=max(d[i-1][j],d[i][j+1]);
            }
        }
    }
    return d[n-1][0];
}
int main(){
    char s[1000];
    cin>>s;
    cout<<dp(s)<<endl;
}

发表于 2019-07-22 18:12:04 回复(0)
lentolove头像 lentolove

图片说明 

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

/**
 * 求最长回文子串的问题，一般有两种方法
 * 1.动态规划
 * 2.中心扩散方法
 */
public class Solution8_回文字符串 {

    /**
     * 最长文回串 ，非连续
     * 动态规划
     */
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        int n = s.length();
        int[][] dp = new int[n][n];//dp[l][r]表示l-r中的最长回文串
        for (int r = 0; r < n; r++) {
            dp[r][r] = 1;
            for (int l = r - 1; l >= 0; l--) {
                if (s.charAt(l) == s.charAt(r)) {
                    dp[l][r] = dp[l + 1][r - 1] + 2;
                }else {
                    dp[l][r] = Math.max(dp[l+1][r],dp[l][r-1]);
                }
            }
        }
        System.out.println(dp[0][n-1]);
    }
}

既然刷到了这个题，还是要介绍一下最原始的求解最长回文子串的问题，即回文串是连续的。
图片说明 

public class Solution144_5_最长回文子串 {

    /**
     * 方法一：中心扩展法
     * 1.既然是回文字符串，本来联想的是滑动窗口，双指针这样的思想，发现并不行，
     * 无法确保 abcd...这一段是否是回文串，万一继续后面是dcba，总不能全部遍历吧，那就等于暴力算法了。
     * 2.回文串的特点，由中间到两边扩散，aba 或者 bb这样的形式，这就需要我们分情况讨论了。
     * for循环以每一个点为中心，求最长文回串，从中心点向两边延伸，记录最长子串
     */

    private int start, maxLen;

    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;
        for (int i = 0; i < s.length(); i++) {
            //考虑两种情况1:aba  和 2: bb
            findMaxPalindrome(s, i, i);
            findMaxPalindrome(s, i, i + 1);
        }
        return s.substring(start, start + maxLen);
    }

    private void findMaxPalindrome(String s, int i, int j) {
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;//向左延伸
            j++;//向右延伸
        }
        //记录每个起始点扩展的回文串的最大长度
        if (maxLen < j - i - 1) {
            start = i + 1;
            maxLen = j - i - 1;
        }
    }

    /**
     * 方法二：动态规划
     * 求解 "最优子结构" 问题，可以考虑用 "动态规划"
     */
    public String longestPalindrome1(String s) {
        int n = s.length();
        if (n < 2) return s;
        int maxLen = 1;
        String res = s.substring(0, 1);
        boolean[][] dp = new boolean[n][n];
        //左边界一定小于右边界，因此从右边界开始
        for (int r = 1; r < n; r++) { //表示右边界
            for (int l = 0; l < r; l++) { //表示左边界
                // 区间应该慢慢放大
                // 状态转移方程：如果头尾字符相等并且中间也是回文
                // 在头尾字符相等的前提下，如果收缩以后不构成区间（最多只有 1 个元素），直接返回 True 即可
                // 否则要继续看收缩以后的区间的回文性
                if (s.charAt(l) == s.charAt(r) && ((r - l) <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        res = s.substring(l, r + 1);
                    }
                }
            }
        }
        return res;
    }
}
编辑于 2019-08-03 21:19:21 回复(4)
C/C++
ElonB头像 ElonB 
/*
考虑动态规划
dp[i][j]表示第i个字符到第j个字符中包含的最大回文子串的最大长度
i:j->0若a[i]与a[j]有相同的字符，则最大长度为dp[i+1][j-1]+2;
否则为以下最大值 max(dp[i+1][j],dp[i][j-1])
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1000

char a[N];
int dp[N][N];

int main()
{
//    freopen("input.txt", "r", stdin);
    int n, i, j, k;
    cin >> a;
    n = strlen(a);
    for(j = 0; j < n; j++) {
        dp[j][j] = 1;
        for(i = j - 1; i >= 0; i--) {
            if(a[i] == a[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[0][n - 1] << endl;
    return 0;
}

编辑于 2019-07-08 20:16:20 回复(0)
heimingsheng头像 heimingsheng
#正串和反串的公共子串
s = input()
l = list(s)
l.reverse()
r = "".join(l)
#求公共串
n = len(s)
dp = [[0 for j in range(n+1)]for i in range(n+1)]

#
for i in range(1,n+1):
    for j in range(1,n+1):
        if s[i-1] == r[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
print(dp[n][n])
发表于 2019-08-10 11:55:33 回复(0)
我还有机会🐎头像 我还有机会🐎 
def dpMaxLenHuiwen(s):
    if not s:
        return
    n = len(s)
    if n == 1:
        return 1
    # d[i][j]为从j到i的字符串中包含的最大回文子串的长度
    d = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        d[i][i] = 1    # 初始化s[i]=1，因为一个字符串的回文就是1
        for j in range(i-1,-1,-1):    # 
            if(s[i] == s[j]):
                d[i][j] = d[i-1][j+1] + 2    # 两边相等，最大回文长度+2
            else:
                d[i][j] = max(d[i-1][j], d[i][j+1])    #两边不相等，最大回文长度为两个最大子串中的最大回文长度
    return d[n-1][0]

s = input()
print(dpMaxLenHuiwen(s))


发表于 2020-12-11 17:43:57 回复(0)
tuweilong头像 tuweilong 
/*
动态规划。
dp[i][j]表示第i个字符到第j个字符中包含的非连续回文长度。
转移方程：
在一个串后面加一个字符x，如果前面没有和x一样的，那包含的非连续回文长度和没加x之前一样。
如果有和x一样的，那需要比较没加x之前的长度 和 两个x之间的回文长度+2 两者的大小。
即dp[beg][end] = Math.max(dp[beg][end - 1], dp[loc + 1][end - 1] + 2)

*/
import java.util.*;
public class Main {
    static String s;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        s = in.next();
        int len = s.length();
        int[][] dp = new int[len + 1][len + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= len; i++) {
            dp[i][i] = 1;
        }
        for (int end = 1; end <= len; end++)
            for (int beg = 1; beg < end; beg++) {
                dp[beg][end] = dp[beg][end - 1];
                for (int loc = beg; loc < end; loc++) {
                    if (s.charAt(loc - 1) == s.charAt(end - 1)) {
                        dp[beg][end] = Math.max(dp[beg][end - 1], dp[loc + 1][end - 1] + 2);
                        break;
                    }
                }
            }
        System.out.println(dp[1][len]);
    }
}

发表于 2019-06-28 14:10:01 回复(0)
Python
贾志统头像 贾志统 
def max_sub_str_length(raw_str):
    dp = {}
    def length_from_l_to_r(l, r):
        if l == r:
            return 1
        if l > r:
            return 0
        if (l, r) in dp:
            return dp[(l, r)]
        sub_str_length = 0
        if raw_str[l] == raw_str[r]:
            sub_str_length = 2 + length_from_l_to_r(l+1, r-1)
        else:
            sub_str_length = max(length_from_l_to_r(l+1, r), length_from_l_to_r(l, r-1))
        dp[(l, r)] = sub_str_length
        return sub_str_length
    return length_from_l_to_r(0, len(raw_str)-1)


raw_str = input()
print(max_sub_str_length(raw_str))

发表于 2019-08-22 19:05:38 回复(0)
牛客700653989号头像 牛客700653989号 
s = input()
dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
for i in range(len(s) - 1, -1, -1):
    dp[i][i] = 1
    for j in range(i + 1, len(s)):
        if s[i] == s[j]:
            dp[i][j] = dp[i + 1][j - 1] + 2
        else:
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
print(dp[0][-1])

发表于 2020-04-08 13:39:31 回复(0)
Nathan_Wu头像 Nathan_Wu
C++ lcs solution 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int longestPalindromeSubseq(string& s) 
{
    vector<vector<int>> dp(s.size() + 1, vector<int>(s.size() + 1));
    for(int i = 1; i <= s.size(); i++)
    {
        for(int j = 1; j <= s.size(); j++)
        {
            if(s[i - 1] == s[s.size() - j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[s.size()][s.size()];
}

int main()
{
    string s;
    cin >> s;
    cout << longestPalindromeSubseq(s) << endl;
    return 0;
}

编辑于 2020-01-18 07:40:36 回复(0)
C/C++
喜欢ctrl的cxk头像 喜欢ctrl的cxk 
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    string str;
    cin >> str;
    int n = str.length();
    int dp[n][n] = {0};    //dp[l][r]表示l-r中的最长回文串
    for(int r = 0; r < n; r++)
    {
        dp[r][r] = 1;
        for(int l = r-1; l >= 0; l--)
        {
            if(str[l] == str[r])
            {
                dp[l][r] = dp[l+1][r-1]+2;
            }
            else
            {
                dp[l][r] = max(dp[l+1][r],dp[l][r-1]);
            }
        }
    }
    cout << dp[0][n-1] << endl;
    return 0;
}

编辑于 2019-12-08 21:42:11 回复(0)
AlanHunter头像 AlanHunter 
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            String s = input.next();
            char[] c = s.toCharArray();
            int len = c.length;
            int[][] dp = new int[len][len];
            for (int r = 0; r < len; r++) {
                dp[r][r] = 1;
                for (int l = r - 1; l >= 0; l--) {
                    if (c[r] == c[l]) {
                        dp[l][r] = dp[l + 1][r - 1] + 2;
                    } else {
                        dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
                    }
                }
            }
            System.out.println(dp[0][len - 1]);
        }
    }
}

发表于 2019-09-25 16:50:15 回复(0)
theflood头像 theflood 
#include <iostream>
#include <istream>
#include <string>
#include <vector>
using namespace std;

int main(){
    
    string s;
    cin >> s;
    
    int n = s.size();
    
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for(int i = 0; i<n; i++){
        dp[i][i] = 1;
    }
    
    for(int i = 1; i<n; i++){
        for(int j = i-1; j>=0; j--){//注意一定要从近到远
            if(s[i] == s[j]){
                if(j+2 <= i) dp[j][i] = max(dp[j][i], dp[j+1][i-1]+2);//j,i不挨着
                else dp[j][i] = 2; //j,i挨着
            } else{
                //j,i之间的最长回文要么是j+1~i，要么是j~i-1
                dp[j][i] = max(dp[j][i], dp[j+1][i]);
                dp[j][i] = max(dp[j][i], dp[j][i-1]);
            }
        }
    }
    
    cout << dp[0][n-1] << endl;
    return 0;
}

发表于 2019-09-17 20:16:30 回复(0)
freezerhan头像 freezerhan 
#include <bits/stdc++.h>

using namespace std;

int f[1002][1002];

int main(){
  string s;
  cin >> s;
  for (int i = s.length() - 1; i >= 0; i--){
    for (int j = 0; j < s.length(); j++){
      if(i > j){
        f[i][j] = 0;
      } else if(i == j){
        f[i][j] = 1;
      } else{
        if(s[i] == s[j]){
          f[i][j] = f[i+1][j-1] + 2;
        } else {
          f[i][j] = max(f[i+1][j], f[i][j-1]);
        }
      }
    }
  }
  cout << f[0][s.length() - 1] << "\n";
  return 0;
}

发表于 2019-09-08 09:36:41 回复(0)
Lwqcpp头像 Lwqcpp
使用动态规划 
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string str;
    cin >> str;
    int size = str.size();
    int dp[size][size];
    for(int i = size-1; i >= 0; i--)
    {
        for(int j = i; j < size; j++)
        {
            if(i==j)
                dp[i][j] = 1;
            else if(str[i] == str[j])
            {
                if(i+1 <= j-1)
                    dp[i][j] = dp[i+1][j-1] + 2;
                else
                    dp[i][j] = 2;
            }
            else
            {
                dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
            }
        }
    }
    cout << dp[0][size-1] << endl;
    return 0;
}


发表于 2019-08-18 20:26:45 回复(0)
巨乖头像 巨乖 
import sys
def fun(string):
    length = len(string)
    if length==0 or length==1:
        return length
    else:
        dp = []
        for i in range(length):
            dp.append([0]*length)
        for i in range(length):
            dp[i][i] = 1
        for k in range(1,length):
            for j in range(length):
                if j + k >=length:
                    continue
                else:
                    if string[j] == string[j+k]:
                        dp[j][j+k] = dp[j+1][j+k-1] + 2
                    else:
                        dp[j][j+k] = max(dp[j+1][j+k],dp[j][j+k-1])
        return dp[0][length-1]
if __name__ == "__main__":
    string = sys.stdin.readline().strip()
    print(fun(string))

发表于 2019-08-08 14:19:35 回复(0)
正在卷的三文鱼很讨厌吃香菜头像 正在卷的三文鱼很讨厌吃香菜
参考楼上大佬的解答，改了一下实现，思路还是一样的。。。 
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        char[] chars=sc.nextLine().toCharArray();
        int len=chars.length;
        int[][] dp=new int[len][len];
        for(int i=0;i<len;i++){
            dp[i][i]=1;
        }
        /*
         注意这里的循环，外层循环是end，内层循环是beg,顺序不能反
         因为求dp[beg][end]的过程依赖于beg之后的值
         */
        for(int end=1;end<len;end++){
            for(int beg=0;beg<end;beg++){
                dp[beg][end]=dp[beg][end-1];
                for(int t=beg;t<end;t++){
                    if(chars[t]==chars[end]){
                        dp[beg][end]=Math.max(dp[beg][end-1],dp[t+1][end-1]+2);
                        break;
                    }
                }
            }
        }
        System.out.println(dp[0][len-1]);
    }
}


发表于 2019-08-06 19:34:50 回复(0)
吃个大西瓜儿头像 吃个大西瓜儿 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;
    int N = s.size();
    vector<vector<int>> dp(N, vector<int>(N, 0));
    
    /* 注释中的部分无法通过全部样例, 有人能帮忙看下吗
    for(int i = 0; i < N; i++) {
        dp[i][i] = 1;
        if(i+1 < N && s[i] == s[i+1])
            dp[i][i+1] = 2;
    }
    
    for(int len = 3; len <= N; len++) {
        for(int left = 0; left + len - 1 < N; left++) {
            int right = left + len - 1;
            dp[left][right] = max(dp[left+1][right], dp[left][right-1]);
            if(s[left] == s[right])
                dp[left][right] = max(dp[left][right], dp[left+1][right-1] + 2);
        }
    }
    */
    
    for(int i = 0; i < N; i++) {
        dp[i][i] = 1;
        for(int j = i - 1; j >= 0; j--) {
            dp[j][i] = max(dp[j+1][i], dp[j][i-1]);
            if(s[j] == s[i])
                dp[j][i] = max(dp[j][i], 2 + dp[j+1][i-1]);
        }
    }
    
    cout << dp[0][N-1] << endl;
    return 0;
}

发表于 2019-08-02 20:21:36 回复(0)
simultaneous头像 simultaneous

转化为求解s和s_reverse的最大公共子串

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
    string s;
    cin >> s;
    string t(s);
    reverse(t.begin(), t.end());
    int n = s.size();
    vector<vector<int>> dp(n+1, vector<int>(n+1));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(s[i] == t[j])
                dp[i+1][j+1] = dp[i][j] + 1;
            else
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
        }
    }
    cout << dp[n][n] << endl;
}
发表于 2019-08-01 14:48:55 回复(0)
Polestar_a头像 Polestar_a 
s = input()
n = len(s)
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n-1, -1, -1):
    dp[i][i] = 1
    for j in range(i+1, n):
        if s[i]==s[j]:
            dp[i][j] = 2+dp[i+1][j-1]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i][j-1])
print(dp[0][-1])

发表于 2019-07-06 18:11:15 回复(0)
提交观点

问题信息

动态规划 快手 字符串 算法工程师 2019
上传者：小小
难度：
22条回答 9942浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号