Problem
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"
Solution: DP
Try all possible i and find the longest palindromic string whose center is i (odd case) and i / i + 1 (even case).
Time complexity: O(n^2)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua, 16 ms, 8.7 MB class Solution { public: string longestPalindrome(string s) { const int n = s.length(); auto getLen = [&](int l, int r) { while (l >= 0 && r < n && s[l] == s[r]) { --l; ++r; } return r - l - 1; }; int len = 0; int start = 0; for (int i = 0; i < n; ++i) { int cur = max(getLen(i, i), getLen(i, i + 1)); if (cur > len) { len = cur; start = i - (len - 1) / 2; } } return s.substr(start, len); } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua, 6 ms， 36.5 MB class Solution { public String longestPalindrome(String s) { int len = 0; int start = 0; for (int i = 0; i < s.length(); ++i) { int cur = Math.max(getLen(s, i, i), getLen(s, i, i + 1)); if (cur > len) { len = cur; start = i - (cur - 1) / 2; } } return s.substring(start, start + len); } private int getLen(String s, int l, int r) { while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { --l; ++r; } return r - l - 1; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# Author: Huahua, 812 ms, 12.7MB class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) def getLen(l, r): while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 return r - l - 1 start = 0 length = 0 for i in range(n): cur = max(getLen(i, i), getLen(i, i + 1)) if cur <= length: continue length = cur start = i - (cur - 1) // 2 return s[start : start + length] |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment