{"id":3917,"date":"2018-09-12T00:45:12","date_gmt":"2018-09-12T07:45:12","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3917"},"modified":"2020-01-02T21:23:36","modified_gmt":"2020-01-03T05:23:36","slug":"leetcode-5-longest-palindromic-substring","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-5-longest-palindromic-substring\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 5. Longest Palindromic Substring"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given a string s<\/strong>, find the longest palindromic substring in s<\/strong>. You may assume that the maximum length of s<\/strong> is 1000.<\/p>\n

Example 1:<\/strong><\/p>\n

Input:<\/strong> \"babad\"\nOutput:<\/strong> \"bab\"\nNote:<\/strong> \"aba\" is also a valid answer.\n<\/pre>\n
Example 2:<\/strong><\/p>\n
Input:<\/strong> \"cbbd\"\nOutput:<\/strong> \"bb\"\n<\/pre>\n
Solution: DP<\/strong><\/h1>\n
Try all possible i and find the longest palindromic string whose center is i (odd case) and i \/ i + 1 (even case).<\/p>\n
Time complexity: O(n^2)<\/p>\n
Space complexity: O(1)<\/p>\n
\n
C++<\/h2>\n
\n\n
\/\/ Author: Huahua, 16 ms, 8.7 MB\nclass Solution {\npublic:\n  string longestPalindrome(string s) {\n    const int n = s.length();\n    auto getLen = [&](int l, int r) {\n      while (l >= 0 && r < n \n             && s[l] == s[r]) {\n        --l;\n        ++r;\n      }\n      return r - l - 1;\n    };\n    int len = 0;\n    int start = 0;\n    for (int i = 0; i < n; ++i) {\n      int cur = max(getLen(i, i), \n                    getLen(i, i + 1));\n      if (cur > len) {\n        len = cur;\n        start = i - (len - 1) \/ 2;\n      }\n    }\n    return s.substr(start, len);\n  }\n};\n\n<\/pre>\n<\/div><\/div>\n
\n
Java<\/h2>\n
\n\n
\/\/ Author: Huahua, 6 ms\uff0c 36.5 MB\nclass Solution {\n  public String longestPalindrome(String s) {\n    int len = 0;\n    int start = 0;\n    for (int i = 0; i < s.length(); ++i) {\n      int cur = Math.max(getLen(s, i, i), \n                         getLen(s, i, i + 1));\n      if (cur > len) {\n        len = cur;\n        start = i - (cur - 1) \/ 2;\n      }\n    }\n    return s.substring(start, start + len);\n  }\n  \n  private int getLen(String s, int l, int r) {\n    while (l >= 0 && r < s.length() \n           && s.charAt(l) == s.charAt(r)) {\n      --l;\n      ++r;\n    }\n    return r - l - 1;\n  }\n}\n<\/pre>\n<\/div><\/div>\n
\n
Python3<\/h2>\n
\n\n
# Author: Huahua, 812 ms, 12.7MB\nclass Solution:\n  def longestPalindrome(self, s: str) -> str:\n    n = len(s)\n    def getLen(l, r):\n      while l >= 0 and r < n and s[l] == s[r]:\n        l -= 1\n        r += 1\n      return r - l - 1\n    \n    start = 0\n    length = 0    \n    for i in range(n):      \n      cur = max(getLen(i, i),\n                getLen(i, i + 1))\n      if cur <= length: continue\n      length = cur\n      start = i - (cur - 1) \/\/ 2\n    return s[start : start + length]\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
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”…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,117,177,498,95,4],"class_list":["post-3917","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-longest","tag-medium","tag-on2","tag-palindrome","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3917","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3917"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3917\/revisions"}],"predecessor-version":[{"id":6044,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3917\/revisions\/6044"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3917"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3917"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3917"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}