当前位置:首页 » 《随便一记》 » 正文

【算法】L2-008 最长对称子串 (25 分)Java,字符串典型例题_m0_57099044的博客

14 人参与  2022年04月03日 09:27  分类 : 《随便一记》  评论

点击全文阅读


L2-008 最长对称子串 (25 分)

对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。

输入格式:

输入在一行中给出长度不超过1000的非空字符串。

输出格式:

在一行中输出最长对称子串的长度。

输入样例:

Is PAT&TAP symmetric?

结尾无空行

输出样例:

11

结尾无空行

这是一个典型的动态规划题

解法:

1:初始化一个dp表格,表格的行表示子串的头下表,表格的列表示子串的尾下标。故对角线上的值都为true

2:对表格的上三角进行列遍历,自左上向右下。若子串的长度为2时,第一个字符与第二个字符相当那么dp[i][j]=true。若长度大于2时,当s[i][j]相等时还需要对中间的子串进行判断。如图中的dp[0][4],需要判断dp[1][3]是否为true。


import java.util.Scanner;

/**
 * L2-008 最长对称子串 (25 分)
 * 对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。
 *
 * 输入格式:
 * 输入在一行中给出长度不超过1000的非空字符串。
 *
 * 输出格式:
 * 在一行中输出最长对称子串的长度。
 *
 * 输入样例:
 * Is PAT&TAP symmetric?
 * 结尾无空行
 * 输出样例:
 * 11
 */
public class L2_008 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        System.out.println(longest(s));
    }
    public static int longest(String s){
        int n=s.length();
        if(s.length()<2)return n;
        int count=1;
        boolean dp[][]=new boolean[n][n];
        //初始化对角线上的单个子串为true
        for(int i=0;i<n;i++){
            dp[i][i]=true;
        }
        char[] chars = s.toCharArray();
        //自左上向右下遍历
        //i表示子串的头,j表示子串的尾
        for(int j=0;j<n;j++){
            for(int i=0;i<j;i++){
                //若
            if(chars[i]!=chars[j])dp[i][j]=false;
            else {
                if(j-i<2)dp[i][j]=true;
                else dp[i][j]=dp[i+1][j-1];
            }
            if(dp[i][j]==true){
                count=Math.max(count,j-i+1);
            }
            }
        }

        return count;
    }

}

 

 

 


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/37206.html

对称  输出  最长  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 我在回忆里万劫不复精彩节选(秦见鹿谢梵声)_我在回忆里万劫不复精彩节选
  • 迟迟白日晚全书+后续(路星延宋栀年)_(迟迟白日晚全书+后续)迟迟白日晚全书+后续列表_笔趣阁(路星延宋栀年)
  • 往梦难复温+全书+后续(沈淮霆宋思予)列表_往梦难复温(沈淮霆宋思予)往梦难复温+全书+后续在线
  • 兰因絮果,爱恨全如玉碎全书+后续+结局(谢长乐肖风行)列表_兰因絮果,爱恨全如玉碎(谢长乐肖风行)兰因絮果,爱恨全如玉碎全书+后续+结局在线
  • 从此星辰远,归途似海深人气节选(璃月龙影)全书免费_(璃月龙影)从此星辰远,归途似海深人气节选后续(璃月龙影)
  • 全文你来时风起云涌番外+(陆翊夏天瑜赵歆)列表_全文你来时风起云涌番外+
  • 人面兽小说精彩节选免费试读_小浩言语小蕊爆款小说高能章节试读
  • 你来时风起云涌免费(陆翊夏天瑜赵歆)
  • 四海八荒苦封喉,君心似毒酒结局+番外+后续看点十足(洛虞玄澈)_四海八荒苦封喉,君心似毒酒结局+番外+后续看点十足(洛虞玄澈)洛虞玄澈免费列表_笔趣阁(洛虞玄澈)
  • 「错宠假千金,全京城权贵暴虐侯府」章节多结局预体验‌_沈轻漾楚珩完结版免费在线阅读
  • 画地为牢(池念谢宴清)_画地为牢(池念谢宴清)
  • 完结文往梦难复温列表_完结文往梦难复温(沈淮霆宋思予)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1