{"id":4110,"date":"2018-10-02T00:40:04","date_gmt":"2018-10-02T07:40:04","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4110"},"modified":"2018-10-02T00:44:12","modified_gmt":"2018-10-02T07:44:12","slug":"leetcode-20-valid-parentheses","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-20-valid-parentheses\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 20. Valid Parentheses"},"content":{"rendered":"

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

Given a string containing just the characters\u00a0'('<\/code>,\u00a0')'<\/code>,\u00a0'{'<\/code>,\u00a0'}'<\/code>,\u00a0'['<\/code>\u00a0and\u00a0']'<\/code>, determine if the input string is valid.<\/p>\n

An input string is valid if:<\/p>\n

    \n
  1. Open brackets must be closed by the same type of brackets.<\/li>\n
  2. Open brackets must be closed in the correct order.<\/li>\n<\/ol>\n

    Note that an empty string is\u00a0also considered valid.<\/p>\n

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

    Input:<\/strong> \"()\"\r\nOutput:<\/strong> true\r\n<\/pre>\n
    Example 2:<\/strong><\/p>\n
    Input:<\/strong> \"()[]{}\"\r\nOutput:<\/strong> true\r\n<\/pre>\n
    Example 3:<\/strong><\/p>\n
    Input:<\/strong> \"(]\"\r\nOutput:<\/strong> false\r\n<\/pre>\n
    Example 4:<\/strong><\/p>\n
    Input:<\/strong> \"([)]\"\r\nOutput:<\/strong> false\r\n<\/pre>\n
    Example 5:<\/strong><\/p>\n
    Input:<\/strong> \"{[]}\"\r\nOutput:<\/strong> true\r\n<\/pre>\n
    Solution: Stack<\/strong><\/h1>\n
    Using a stack to track the existing open parentheses, if the current one is a close\u00a0parenthesis but does not match the top of the stack, return false, otherwise pop the stack. Check whether the stack is empty in the end.<\/p>\n
    Time complexity: O(n)<\/p>\n
    Space complexity: O(n)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua, 0 ms\r\nclass Solution {\r\npublic:\r\n  bool isValid(string s) {\r\n    map<char, char> p{{')', '('}, {']', '['}, {'}', '{'}};\r\n    stack<char> st;    \r\n    for (char c : s) {\r\n      if (!p.count(c)) {\r\n        st.push(c);\r\n      } else {\r\n        if (st.empty() || p[c] != st.top()) return false;        \r\n        st.pop();\r\n      }\r\n    }\r\n    return st.empty();\r\n  }\r\n};<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    # Author: Huahua\r\nclass Solution:\r\n  def isValid(self, s):\r\n    p = {')' : '(', ']': '[', '}' : '{'}\r\n    stack = []\r\n    for c in s:\r\n      if c not in p:\r\n        stack.append(c)\r\n      else:\r\n        if not stack or stack[-1] != p[c]: return False\r\n        stack.pop()\r\n    return not stack<\/pre>\n<\/div><\/div>\n
    Related Problems<\/strong><\/h1>\n