20_Valid_Parentheses.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "20. Valid Parentheses.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7LI0zRL2iTta"
      },
      "source": [
        "**Problem Statement :**\n",
        "\n",
        "Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.\n",
        "\n",
        "An input string is valid if:\n",
        "\n",
        "Open brackets must be closed by the same type of brackets.\n",
        "Open brackets must be closed in the correct order.\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "Input: s = \"()\"\n",
        "\n",
        "Output: true\n",
        "\n",
        "Example 2:\n",
        "\n",
        "Input: s = \"()[]{}\"\n",
        "\n",
        "Output: true"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Cdw_swt2iOxx"
      },
      "source": [
        "## Time Complexity : O(n)\n",
        "## Space Complexity : O(n)\n",
        "## Data Structure Used : Stack\n",
        "class Solution:\n",
        "    def isValid(self, s: str) -> bool:\n",
        "        stack = []\n",
        "        mapping = {\"(\" : \")\", \"{\" : \"}\", \"[\" : \"]\"}\n",
        "        open_parameters = set([\"(\", \"[\", \"{\"])\n",
        "        \n",
        "        for char in s:\n",
        "            if char in open_parameters:\n",
        "                stack.append(char)\n",
        "            elif stack and char == mapping[stack[-1]]:\n",
        "                stack.pop()\n",
        "            else:\n",
        "                return False\n",
        "        return stack == []"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}