{"id":5054,"date":"2022-06-19T15:02:00","date_gmt":"2022-06-19T20:02:00","guid":{"rendered":"https:\/\/wanderin.dev\/?p=5054"},"modified":"2024-10-06T10:10:07","modified_gmt":"2024-10-06T15:10:07","slug":"valid-parentheses-leetcode-20","status":"publish","type":"post","link":"https:\/\/wanderin.dev\/coding-challenges\/valid-parentheses-leetcode-20\/","title":{"rendered":"Valid Parentheses (LeetCode #20)"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\" id=\"h-challenge-statement\">Challenge Statement<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>Given a string <em>s<\/em> containing just the characters &#8216;(&#8216;, &#8216;)&#8217;, &#8216;{&#8216;, &#8216;}&#8217;, &#8216;[&#8216; and &#8216;]&#8217;, determine if the input string is valid.<\/li><li>An input string is valid if:<ul><li>Open brackets must be closed by the same type of brackets.<\/li><li>Open brackets must be closed in the correct order.<\/li><\/ul><\/li><li>This challenge corresponds to&nbsp;<a href=\"https:\/\/leetcode.com\/problems\/valid-parentheses\/\" target=\"_blank\" rel=\"noreferrer noopener\">LeetCode #20<\/a>.<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"h-constraints\"><strong>Constraints<\/strong><\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= s.length &lt;= 10<sup>4<\/sup> <\/code><\/li><li><code>s<\/code> consists of parentheses only &#8216;()[]{}&#8217;.<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"h-example-1\"><strong>Example 1:<\/strong><\/h3>\n\n\n\n<p><strong>Input:<\/strong>&nbsp;<code>s = \"()\"<\/code><\/p>\n\n\n\n<p><strong>Output:<\/strong>&nbsp;<code>True<\/code><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"h-example-2\"><strong>Example 2:<\/strong><\/h3>\n\n\n\n<p><strong>Input:<\/strong><code>&nbsp;s = \"()[]{}\"<\/code><\/p>\n\n\n\n<p><strong>Output:<\/strong>&nbsp;<code>True<\/code><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"h-example-3\"><strong>Example 3:<\/strong><\/h3>\n\n\n\n<p><strong>Input:<\/strong>&nbsp;<code>s = \"(]\"<\/code><\/p>\n\n\n\n<p><strong>Output:<\/strong>&nbsp;<code>False<\/code><\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-solution\">Solution<\/h2>\n\n\n\n<p>Below is my solution and some test cases.  The solution has a<strong> linear time complexity of O(n) <\/strong>and a <strong>linear space complexity O(n)<\/strong>, where n is the length of the string&nbsp;<em>s<\/em>.<\/p>\n\n\n\n<script src=\"https:\/\/gist.github.com\/wanderindev\/82e7b3172d9d6ab18e9230ad6c857f71.js\"><\/script>\n","protected":false},"excerpt":{"rendered":"<p>This post contains my solution to LeetCode&#8217;s problem #20, Valid Parentheses.<\/p>\n","protected":false},"author":152069353,"featured_media":5285,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_coblocks_attr":"","_coblocks_dimensions":"","_coblocks_responsive_height":"","_coblocks_accordion_ie_support":"","footnotes":""},"categories":[4504556,4504566],"tags":[4504555,4504569,4504573],"class_list":["post-5054","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coding-challenges","category-easy","tag-coding-challenge","tag-easy","tag-stack"],"jetpack_featured_media_url":"https:\/\/wanderin.dev\/wp-content\/uploads\/2022\/07\/20.png","amp_enabled":true,"_links":{"self":[{"href":"https:\/\/wanderin.dev\/wp-json\/wp\/v2\/posts\/5054","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wanderin.dev\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wanderin.dev\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wanderin.dev\/wp-json\/wp\/v2\/users\/152069353"}],"replies":[{"embeddable":true,"href":"https:\/\/wanderin.dev\/wp-json\/wp\/v2\/comments?post=5054"}],"version-history":[{"count":6,"href":"https:\/\/wanderin.dev\/wp-json\/wp\/v2\/posts\/5054\/revisions"}],"predecessor-version":[{"id":5329,"href":"https:\/\/wanderin.dev\/wp-json\/wp\/v2\/posts\/5054\/revisions\/5329"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wanderin.dev\/wp-json\/wp\/v2\/media\/5285"}],"wp:attachment":[{"href":"https:\/\/wanderin.dev\/wp-json\/wp\/v2\/media?parent=5054"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wanderin.dev\/wp-json\/wp\/v2\/categories?post=5054"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wanderin.dev\/wp-json\/wp\/v2\/tags?post=5054"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}