solution_python/005 Longest Palindromic Substring.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 005 Longest Palindromic Substring\n",
    "- 笔记作者：CV七少\n",
    "- 学习时间：2020.6.7\n",
    "- 编程语言：python\n",
    "- 学习任务：leetcode题解\n",
    "- 题目地址：https://leetcode-cn.com/problems/longest-palindromic-substring/  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目:\n",
    "\n",
    "给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 示例：\n",
    "- 示例 1\n",
    "    ```\n",
    "    输入: \"babad\"\n",
    "    输出: \"bab\"\n",
    "    注意: \"aba\" 也是一个有效答案。\n",
    "    ```\n",
    "- 示例 2\n",
    "    ```\n",
    "    输入: \"cbbd\"\n",
    "    输出: \"bb\"\n",
    "    ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " <font color=#008000>**方法一：**</font>暴力搜索法<br>\n",
    "- 思路核心：根据回文子串的定义，枚举所有长度大于等于2的子串，依次判断它们是否是回文\n",
    "- 实现要点：\n",
    "    1. 在具体实现时，可以只针对大于“当前得到的最长回文子串长度”的子串进行“回文验证”；\n",
    "    2. 在记录最长回文子串的时候，可以只记录“当前子串的起始位置”和“子串长度”，不必做截取。这一步我们放在后面的方法中实现。\n",
    "- 时间复杂度$O(n^3)$，空间复杂度$O(1)$\n",
    "```\n",
    "执行用时 :6840 ms, 在所有 Python3 提交中击败了8.31%的用户\n",
    "内存消耗 :13.8 MB, 在所有 Python3 提交中击败了9.26%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： bab\n"
     ]
    }
   ],
   "source": [
    "class Solution1:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"   \n",
    "        max_len = start = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i,len(s)):\n",
    "                if j-i+1 > max_len and s[i:j+1] == s[i:j+1][::-1]:\n",
    "                    max_len = j-i+1\n",
    "                    start = i\n",
    "        \n",
    "        return s[start:start+max_len]\n",
    "    \n",
    "\"\"\"\n",
    "For Example:    input:   s = 'babad'\n",
    "               output:   'aba'\n",
    "\"\"\"\n",
    "\n",
    "s = 'babad'\n",
    "                \n",
    "solution = Solution1()\n",
    "result = solution.longestPalindrome(s)\n",
    "print('输出为：', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " <font color=#008000>**方法二：**</font>动态规划<br>\n",
    "- 思路核心：在头尾字符相等的情况下，里面子串的回文性质据定了整个子串的回文性质，这就是状态转移。\n",
    "- 实现要点：状态转移方程：`dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]`\n",
    "- 时间复杂度$O(n^2)$，空间复杂度$O(n^2)$\n",
    "```\n",
    "执行用时 :4884 ms, 在所有 Python3 提交中击败了29.26%的用户\n",
    "内存消耗 :22.2 MB, 在所有 Python3 提交中击败了5.55%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： bab\n"
     ]
    }
   ],
   "source": [
    "class Solution2:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"   \n",
    "        max_len = start = 0\n",
    "        \n",
    "        dp = [[False for _ in range(len(s))] for _ in range(len(s))]\n",
    "        \n",
    "        for j in range(len(s)):\n",
    "            for i in range(j+1):\n",
    "                dp[i][j] = s[i] == s[j] and (j-i < 3 or dp[i+1][j-1])\n",
    "\n",
    "                if dp[i][j]:\n",
    "                    cur_len = j-i+1\n",
    "                    if cur_len > max_len:\n",
    "                        max_len = cur_len\n",
    "                        start = i\n",
    "\n",
    "        return s[start:start+max_len]\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:   s = 'babad'\n",
    "               output:   'aba'\n",
    "\"\"\"\n",
    "\n",
    "s = 'babad'\n",
    "                \n",
    "solution = Solution2()\n",
    "result = solution.longestPalindrome(s)\n",
    "print('输出为：', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法三：**</font>中心扩散法<br>\n",
    "- 思路核心：枚举可能出现的回文子串的“中心位置”，从“中心位置”尝试尽可能扩散出去，得到一个回文串。\n",
    "- 实现要点：扩散的时候奇偶性是不同的，分开来写。\n",
    "- 时间复杂度$O(n^2)$，空间复杂度$O(1)$\n",
    "```\n",
    "执行用时 :1008 ms, 在所有 Python3 提交中击败了79.52%的用户\n",
    "内存消耗 :13.7 MB, 在所有 Python3 提交中击败了9.26%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： bab\n"
     ]
    }
   ],
   "source": [
    "class Solution3:\n",
    "\n",
    "    def expandAroundCenter(self, s, left, right):\n",
    "        while left >= 0 and right < len(s) and s[left] == s[right]:\n",
    "            left -= 1\n",
    "            right += 1\n",
    "        return left+1, right-left-1\n",
    "\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"   \n",
    "        start = max_len = 0\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            start1, cur_len1 = self.expandAroundCenter(s, i, i)\n",
    "            start2, cur_len2 = self.expandAroundCenter(s, i, i+1)\n",
    "            if cur_len1 > max_len:\n",
    "                max_len = cur_len1\n",
    "                start = start1\n",
    "            if cur_len2 > max_len:\n",
    "                max_len = cur_len2\n",
    "                start = start2\n",
    "        return s[start:start+max_len]\n",
    "    \n",
    "\"\"\"\n",
    "For Example:    input:   s = 'babad'\n",
    "               output:   'aba'\n",
    "\"\"\"\n",
    "\n",
    "s = 'babad'\n",
    "                \n",
    "solution = Solution3()\n",
    "result = solution.longestPalindrome(s)\n",
    "print('输出为：', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " <font color=#008000>**方法四：**</font>搜索改进法<br>\n",
    "- 思路核心：我认为这是第一种方法的升级版本。\n",
    "- 实现要点：相当于第二轮搜索只搜索可能是最长子串的两种情况。\n",
    "- 时间复杂度$O(n^2)$，空间复杂度$O(1)$\n",
    "```\n",
    "执行用时 :76 ms, 在所有 Python3 提交中击败了98.46%的用户\n",
    "内存消耗 :13.6 MB, 在所有 Python3 提交中击败了9.26%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： bab\n"
     ]
    }
   ],
   "source": [
    "class Solution4:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"   \n",
    "        res = ''\n",
    "        for i in range(len(s)):\n",
    "            start = max(0, i-len(res)-1)\n",
    "            temp = s[start : i+1]\n",
    "            if temp == temp[::-1]:\n",
    "                res = temp\n",
    "            else:\n",
    "                temp = temp[1:]\n",
    "                if temp == temp[::-1]:\n",
    "                    res = temp\n",
    "        return res\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:   s = 'babad'\n",
    "               output:   'aba'\n",
    "\"\"\"\n",
    "\n",
    "s = 'babad'\n",
    "                \n",
    "solution = Solution3()\n",
    "result = solution.longestPalindrome(s)\n",
    "print('输出为：', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法五：**</font>Manacher算法<br>\n",
    "- 思路核心：Manacher 算法本质上还是中心扩散法，只不过它使用了类似 KMP 算法的技巧，充分挖掘了已经进行回文判定的子串的特点，在遍历的过程中，记录了已经遍历过的子串的信息，也是典型的以空间换时间思想的体现。\n",
    "- 实现要点：这部分可以参考 [题注](https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/)\n",
    "- 时间复杂度$O(n^2)$，空间复杂度$O(1)$\n",
    "```\n",
    "执行用时 :140 ms, 在所有 Python3 提交中击败了92.75%的用户\n",
    "内存消耗 :13.5 MB, 在所有 Python3 提交中击败了9.26%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： bab\n"
     ]
    }
   ],
   "source": [
    "class Solution5:\n",
    "    \n",
    "    def expandAroundCenter(self, s_change, left, right):\n",
    "        while left >= 0 and right < len(s_change) and s_change[left] == s_change[right]:\n",
    "            left -= 1\n",
    "            right += 1\n",
    "        return (right-left-2) // 2\n",
    "\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"   \n",
    "        s_change = '#' + '#'.join(list(s)) + '#'\n",
    "        center = maxRight = max_len = max_center = 0\n",
    "        list_len = []\n",
    "\n",
    "        for i in range(len(s_change)):\n",
    "            if i < maxRight:\n",
    "                i_mirror = 2*center-i\n",
    "                min_len = min(list_len[i_mirror], maxRight-i)\n",
    "                cur_len = self.expandAroundCenter(s_change, i-min_len, i+min_len)\n",
    "            else:\n",
    "                cur_len = self.expandAroundCenter(s_change, i, i)\n",
    "            \n",
    "            list_len.append(cur_len)\n",
    "\n",
    "            if i + cur_len > maxRight:\n",
    "                maxRight = i + cur_len\n",
    "                center = i\n",
    "\n",
    "            if cur_len > max_len:\n",
    "                max_len = cur_len\n",
    "                max_center = i\n",
    "\n",
    "        return s_change[max_center-max_len+1:max_center+max_len:2]\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:   s = 'babad'\n",
    "               output:   'aba'\n",
    "\"\"\"\n",
    "\n",
    "s = 'babad'\n",
    "                \n",
    "solution = Solution3()\n",
    "result = solution.longestPalindrome(s)\n",
    "print('输出为：', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 测试\n",
    "- 提交后的执行用时，只能作为参考，它和很多因素有关，包括数据的维度，数据的特殊性，机器的性能等等    \n",
    "- 而且同样的时间复杂度，由于具体情况的不同，每个复杂度乘以的比例，其他未算入的低阶项等等都会带来不一样的时间损耗  \n",
    "- 甚至同一个算法的不同实现，实际用时都是不一样的\n",
    "- 实际工程也是需要权衡各种利弊，具体问题具体分析"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 'aaaaa'*1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "926 ms ± 28.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "solution = Solution1()\n",
    "result = solution.longestPalindrome(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.43 s ± 116 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "solution = Solution2()\n",
    "result = solution.longestPalindrome(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.12 s ± 4.23 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "solution = Solution3()\n",
    "result = solution.longestPalindrome(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15.6 ms ± 74.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "solution = Solution4()\n",
    "result = solution.longestPalindrome(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9.7 ms ± 24.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "solution = Solution5()\n",
    "result = solution.longestPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "1. https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/\n",
    "2. https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/\n",
    "3. https://www.bilibili.com/video/BV1d7411U7dw?from=search&seid=112685129946594939"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 如果你觉得有用的话：\n",
    "- 请点点 **star** 呦\n",
    "- 关注我的 [CSDN博客](https://mp.csdn.net/console/article)\n",
    "- 关注公众号：CV伴读社\n",
    "<img src='./images/qrcode.jpg' style='zoom:100%'>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}