algorithms/020-valid-parentheses.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "educational-fashion",
   "metadata": {},
   "source": [
    "### 有效的括号\n",
    "\n",
    "给定一个只包括 `'('，')'，'{'，'}'，'['，']'` 的字符串`s`，判断字符串是否有效。\n",
    "\n",
    "有效字符串需满足：\n",
    "1. 左括号必须用相同类型的右括号闭合。\n",
    "2. 左括号必须以正确的顺序闭合。\n",
    "\n",
    "#### 示例 1：\n",
    "```\n",
    "输入：s = \"()\"\n",
    "输出：true\n",
    "```\n",
    "\n",
    "#### 示例 2：\n",
    "```\n",
    "输入：s = \"()[]{}\"\n",
    "输出：true\n",
    "```\n",
    "\n",
    "#### 示例 3：\n",
    "```\n",
    "输入：s = \"(]\"\n",
    "输出：false\n",
    "```\n",
    "\n",
    "#### 示例 4：\n",
    "```\n",
    "输入：s = \"([)]\"\n",
    "输出：false\n",
    "```\n",
    "\n",
    "#### 示例 5：\n",
    "```\n",
    "输入：s = \"{[]}\"\n",
    "输出：true\n",
    "```\n",
    "\n",
    "#### 提示：\n",
    "- `1 <= s.length <= 104`\n",
    "- `s`仅由括号`'()[]{}'`组成"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "optical-picture",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValid(s: str) -> bool:\n",
    "    stack = []\n",
    "    for c in s:\n",
    "        if c == '(' or c == '[' or c == '{' :\n",
    "            stack.append(c)\n",
    "        else:\n",
    "            if len(stack) == 0:\n",
    "                return False\n",
    "            peek = stack[-1]\n",
    "            if c == ')' and peek == '(' or c == ']' and peek == '[' or c == '}' and peek == '{':\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(c)\n",
    "    return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "previous-telling",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"[\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "subtle-liabilities",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"]\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "expressed-coordinate",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"()\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "included-teaching",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid('([)]')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "cosmetic-escape",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"((\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "breathing-building",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"()[]{}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "dutch-anger",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"([)]\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "welcome-award",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"([\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "relative-howard",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"([]\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "electronic-cleanup",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"([])\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "psychological-upset",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"[])\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "reported-pioneer",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"(()])}[}[}[]][}}[}{})][[(]({])])}}(])){)((){\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "lightweight-volume",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"(({}((({}(]([){)}]{){}{))))][\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "unable-emergency",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"[](([[]]){}{[]}([]))\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "interstate-garlic",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"}(])[{(}([[}])}]))})]]({{(])\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "becoming-segment",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"[{[}}])()(})}{}]({}])][({\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "closing-contractor",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"{({))[}()))[{{}(]]([)(({)]]())[)}[([}[(]{\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "elegant-coordination",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"({][])]]]){)[)}]]]}])]{}(\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "discrete-lithuania",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"[][{[{{}}[][]{{}}]}]\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "perceived-calculation",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"{(}{){)}[]}][[[{()]}(()[({({[}{[))(([])[)([])[\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "banner-light",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(\"}{[{]}[{[(([}]({(]([(){){{)][{[\")"
   ]
  }
 ],
 "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}