[数据结构与算法]算法题今日总结（20210802）

1. 最长回文子串

给定一个字符串?s，找到?s?中最长的回文子串

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

解题方法：

1. 动态规划

如果一个字符串是回文串，那么它的子串也是回文串，由此可得：

a. 字符串长度为1时， 该字符串为回文串

b. 字符串长度大于1时，要比较字符串开头字符，结尾字符是否相同，且抛去开头结尾的子串是否为回文串

建立一个二维数组，dp[i][j] 表示开头为i, 结尾为j 的字符串是否为回文串

初始值可确定，i=j 时， dp[i][j] = true;

i != j 时， 分为两种情况??

a. i-j = 1? 判断? dp[i][j] = char[i] == char[j]

b. i-j > 1? ? ?dp[i][j] = dp[i-1][j+1] && (char[i] ==char[j])

以上空间复杂度比较高，继续优化。。。。