首页 > 代码库 > [Leetcode] 5 - Longest Palindromic Substring
[Leetcode] 5 - Longest Palindromic Substring
题目链接:https://oj.leetcode.com/problems/longest-palindromic-substring/
这道题通常可以写出来的是2种做法。
1. 保持一个index从前往后扫,每次index的循环中,保持left和right的index向两边扫,但是有2种情况,aba和abba。left和right的扫描要扫2次
2. DP做法,2维矩阵
* 可以适当减枝,比如当前index完全不可能提供比已经得到的最长string再长的可能,则移动到下一个index
class Solution { public: string longestPalindrome(string s) { if (s.size() == 0) return ""; int idx = 0; int maxLen = 0; string res; while (idx < s.size()) { // break if even the longest palindrome string we could get // is still shorter than the maximun one we have if (min(s.size() - idx, idx + 1) * 2 <= maxLen) break; int left; int right; // 1st case, ex: aba left = idx; right = idx; while (left >= 0 && right < s.size()) { if (s[left] == s[right]) { if (maxLen < right - left + 1) { maxLen = right - left + 1; res = s.substr(left, right - left + 1); } --left; ++right; } else { break; } } // 2nd case, ex: abba left = idx; right = idx + 1; while (left >= 0 && right < s.size()) { if (s[left] == s[right]) { if (maxLen < right - left + 1) { maxLen = right - left + 1; res = s.substr(left, right - left + 1); } --left; ++right; } else { break; } } ++idx; } return res; } };
[Leetcode] 5 - Longest Palindromic Substring
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。