题目地址
https://leetcode.com/problems/longest-palindromic-substring/description/
题目描述
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
思路
这是一道最长回文的题目,要我们求出给定字符串的最大回文子串。
解决这类问题的核心思想就是两个字“延伸”,具体来说
- 如果一个字符串是回文串,那么在它左右分别加上一个相同的字符,那么它一定还是一个回文串
- 如果一个字符串不是回文串,或者在回文串左右分别加不同的字符,得到的一定不是回文串
事实上,上面的分析已经建立了大问题和小问题之间的关联,
基于此,我们可以建立动态规划模型。
我们可以用 dp[i][j] 表示 s 中从 i 到 j(包括 i 和 j)是否可以形成回文,
状态转移方程只是将上面的描述转化为代码即可:
if (s[i] === s[j] && dp[i + 1][j - 1]) { dp[i][j] = true; }
base case就是一个字符(轴对称点是本身),或者两个字符(轴对称点是介于两者之间的虚拟点)。
关键点
- ”延伸“(extend)
代码
/* * @lc app=leetcode id=5 lang=javascript * * [5] Longest Palindromic Substring */ /** * @param {string} s * @return {string} */ var longestPalindrome = function(s) { // babad // tag : dp if (!s || s.length === 0) return ""; let res = s[0]; const dp = []; // 倒着遍历简化操作, 这么做的原因是dp[i][..]依赖于dp[i + 1][..] for (let i = s.length - 1; i >= 0; i--) { dp[i] = []; for (let j = i; j < s.length; j++) { if (j - i === 0) dp[i][j] = true; // specail case 1 else if (j - i === 1 && s[i] === s[j]) dp[i][j] = true; // specail case 2 else if (s[i] === s[j] && dp[i + 1][j - 1]) { // state transition dp[i][j] = true; } if (dp[i][j] && j - i + 1 > res.length) { // update res res = s.slice(i, j + 1); } } } return res; };
相关题目
- 516.longest-palindromic-subsequence
题目地址 https://leetcode.com/problems/longest-consecutive-sequence/description/ 题目描述 Given an unsorted array of integers, find the length of the longest consecutive elements sequence.…
LeetCode题解32.longest-valid-parentheses题目地址 https://leetcode.com/problems/longest-valid-parentheses/ 题目描述 Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) par…
LeetCode题解计算机为什么是基于二进制的?可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系?深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈