2019届vivo校招笔试题第三题

1.题目描述

定义前后两端完全一致的字符串为对称字符串，如“abba”,“caddac”,编写程序，输出字符串"abcdefiiaaovivoovivcaideumncca"的最长对称子字符串。

2.解题思路

同leetcode_【5】最长回文子串：https://blog.csdn.net/qq_17556191/article/details/94620675

以下用动态规划重写：dp[i][j]代表的意思是索引从i到j的子字符串是否是回文，假设s = cbbd,则可以dp对应坐标索引下的子字符串：

	i = 0	1	2	3
j = 0	c	cb	cbb	cbbd
1		b	bb	bbd
2			b	bd
3				d

1.动态规划初始化

• 对角线dp[i][i]:代表当前字符str.charAt(i),故初始化为true
• 相邻的两个字符初始化，两个字符相等就可以了。str.charAt(i) == str.charAt(j)

2.动态规划状态转移矩阵

• 假设要求dp[0][2]，首先还是要判断开头和结尾是否相等，也就是判断 str.charAt(0)==str.charAt(2)，假如此时str.charAt(0)==str.charAt(2)，我们还要再看剩下的子串是否回文， 我们可以直接从dp[i+1][j-1]来判断剩下的子串，把结果直接拿来用,判断是否是true（true表示回文）

  即有公式

  dp[i][j] = dp[i+1][j-1] &&str.charAt(0)==str.charAt(2) ?true:false

3.代码

public class Main {
    public static void main(String[] args) {
        String str = "abcdefiiaaovivoovivcaideumncca";
        solution(str);
    }
    public static void solution(String str){
        char arr[] = str.toCharArray();
        //dp[i][j]代表i~j的字符串的回文长度
        boolean [][]dp = new boolean[str.length()][str.length()];
        //初始化对角线
        for(int i = 0;i<str.length();i++){
            dp[i][i] = true;
        }
        //初始化相邻的两个字符是否为回文
        for(int i = 0;i<=arr.length-2;i++){
            dp[i][i+1] = str.charAt(i) == str.charAt(i+1)?true:false;
        }
        int max = 1;
        String res = "";
        for(int i = 0;i<arr.length;i++){
            for(int j = i+2;j<arr.length;j++){
                    //两端的数相等以及中间的数是回文
                    dp[i][j] = dp[i+1][j-1] && str.charAt(i) == str.charAt(j) ? true:false;
                if(dp[i][j] == true && j - i + 1>max){
                    max = j-i+1;
                    res = str.substring(i,j+1);
                }
            }
        }
        System.out.println(max);
        System.out.println(res);
    }
}

整理自牛客资料技术篇

个人想法，如有错误请指出！！