LeetCode 5. Longest Palindromic Substring (DP)
程序员文章站
2024-03-23 11:27:28
...
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"
注意边界条件,如没有回文串。
class Solution {
int dp[1002][1002];
public:
string longestPalindrome(string str) {
int n =str.size();
for(int i=0;i<n;i++)
dp[i][i] = 1;
int s=0, l = 0;
for(int j=1;j<n;j++)
for(int i=0;i<j;i++) {
if(str[i]==str[j]) {
if(j==i+1) dp[i][j]=1;
else
dp[i][j]=dp[i+1][j-1];
if(dp[i][j] && (j-i+1) >= l) {
l = j-i+1;
s = i;
}
}
}
if(l==0) return str.substr(0, 1);
return str.substr(s, l);
}
};
推荐阅读
-
LeetCode 5. Longest Palindromic Substring (DP)
-
5. Longest Palindromic Substring
-
Given a string s, find the longest palindromic substring in s. You may assume that the maximum lengt
-
LeetCode[字符串] - #3 Longest Substring Without Repeating Characters 博客分类: LeetCode LeetCodeJavaAlgorithm题解String
-
[LeetCode]3. Longest Substring Without Repeating Characters无重复字符的最长子串
-
5. Longest Palindromic Substring (最长回文子序列)
-
leetcode-5:Longest Palindromic Substring 最长回文子串
-
leetcode5:Longest Palindromic Substring最长回文子串
-
LeetCode 5. Longest Palindromic Substring(最长回文子串)
-
leetcode 5. Longest Palindromic Substring 回文串处理