solution_python/010 Regular Expression Matching.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 010 Regular Expression Matching\n",
    "- 笔记作者：CV七少\n",
    "- 学习时间：2020.6.12\n",
    "- 编程语言：python\n",
    "- 学习任务：leetcode题解\n",
    "- 题目地址：https://leetcode-cn.com/problems/regular-expression-matching/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目:\n",
    "\n",
    "给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 `'.'` 和 `'*'` 的正则表达式匹配。\n",
    "```\n",
    "'.' 匹配任意单个字符\n",
    "'*' 匹配零个或多个前面的那一个元素\n",
    "```\n",
    "所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。\n",
    "说明\n",
    "s 可能为空，且只包含从 a-z 的小写字母。\n",
    "p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 示例：\n",
    "示例 1:\n",
    "```\n",
    "输入:\n",
    "s = \"aa\"\n",
    "p = \"a\"\n",
    "输出: false\n",
    "解释: \"a\" 无法匹配 \"aa\" 整个字符串。\n",
    "```\n",
    "示例 2:\n",
    "```\n",
    "输入:\n",
    "s = \"aa\"\n",
    "p = \"a*\"\n",
    "输出: true\n",
    "解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 \"aa\" 可被视为 'a' 重复了一次。\n",
    "```\n",
    "示例 3:\n",
    "```\n",
    "输入:\n",
    "s = \"ab\"\n",
    "p = \".*\"\n",
    "输出: true\n",
    "解释: \".*\" 表示可匹配零个或多个（'*'）任意字符（'.'）。\n",
    "```\n",
    "示例 4:\n",
    "```\n",
    "输入:\n",
    "s = \"aab\"\n",
    "p = \"c*a*b\"\n",
    "输出: true\n",
    "解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 \"aab\"。\n",
    "```\n",
    "示例 5:\n",
    "```\n",
    "输入:\n",
    "s = \"mississippi\"\n",
    "p = \"mis*is*p*.\"\n",
    "输出: false\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法一：**</font> 回溯\n",
    "```\n",
    "执行用时 :1512 ms, 在所有 Python3 提交中击败了19.97%的用户\n",
    "内存消耗 :13.7 MB, 在所有 Python3 提交中击败了6.82%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为: False\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def isMatch(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not p:\n",
    "            return not s\n",
    "\n",
    "        first_match = bool(s) and p[0] in {s[0], '.'}\n",
    "\n",
    "        if len(p) >= 2 and p[1] == '*':\n",
    "            return (self.isMatch(s, p[2:]) or\n",
    "                    first_match and self.isMatch(s[1:], p))\n",
    "        else:\n",
    "            return first_match and self.isMatch(s[1:], p[1:])\n",
    "    \n",
    "\"\"\"\n",
    "For Example:    input:   x = -121\n",
    "               output:   False\n",
    "\"\"\"\n",
    "s = \"mississippi\"\n",
    "p = \"mis*is*p*.\"\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.isMatch(s, p)\n",
    "print('输出为:', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法二：**</font> 动态规划\n",
    "```\n",
    "执行用时 :56 ms, 在所有 Python3 提交中击败了86.07%的用户\n",
    "内存消耗 :13.7 MB, 在所有 Python3 提交中击败了6.82%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为: False\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def isMatch(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        dp = [[False for _ in range(len(s) + 1)] for _ in range(len(p) + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(2, len(p)+1):\n",
    "            dp[i][0] = dp[i-2][0] and p[i-1] == '*'\n",
    "        for i in range(1, len(p) + 1):\n",
    "            for j in range(1, len(s) + 1):\n",
    "                if p[i-1] == '*':\n",
    "                    dp[i][j] = dp[i-2][j] or (dp[i][j-1] and p[i-2] in ['.', s[j-1]])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j-1] and p[i-1] in ['.', s[j-1]]\n",
    "        \n",
    "        return dp[-1][-1]\n",
    "    \n",
    "\"\"\"\n",
    "For Example:    input:   x = -121\n",
    "               output:   False\n",
    "\"\"\"\n",
    "s = \"mississippi\"\n",
    "p = \"mis*is*p*.\"\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.isMatch(s, p)\n",
    "print('输出为:', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "1. https://www.bilibili.com/video/BV1Tt4y1U7QP\n",
    "2. https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-dong-tai-gui-hua-by-jy/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 如果你觉得有用的话：\n",
    "- 请点点 **star** 呦\n",
    "- 关注我的 [CSDN博客](https://mp.csdn.net/console/article)\n",
    "- 关注我的 [哔哩哔哩](https://space.bilibili.com/424394389/channel/detail?cid=132513)\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
}