Skip to main content

Leetcode 20: Valid Parentheses

 

1. Problem Statement (Simple Explanation):


You're given a string s containing only these characters:

  • '(' , ')' , '{' , '}' , '[' , ']'

You must determine if s is a valid parentheses string.

A string is valid if:

  1. Every opening bracket has a matching closing bracket of the same type.

  2. Brackets are closed in the correct order (properly nested).

  3. No extra closing brackets appear without a matching opening bracket.

Return true if valid, otherwise false.


2. Examples:


Example 1:

Input: s = "()"

Output: true


Example 2:

Input: s = "()[]{}"

Output: true
Explanation: "()", "[]", and "{}" are all valid and appear in correct order.


Example 3:

Input: s = "(]"

Output: false
Explanation: ( must be closed by ), not ].


Example 4:

Input: s = "([])"

Output: true
Explanation: Proper nesting: "(" + "[]" + ")".


Example 5:

Input: s = "([)]"

Output: false
Explanation: Order is wrong; '(' is closed after ']', not after ')'.


3. Approach – Stack (Standard Solution):


This is a classic stack problem.


Intuition:


  • Whenever we see an opening bracket ((, {, [), we push it onto the stack.

  • Whenever we see a closing bracket (), }, ]):

    • The stack must not be empty.

    • The top of the stack must be the matching opening bracket.

    • If so, we pop it.

    • Otherwise, the string is invalid.

At the end:

  • If the stack is empty, all brackets are properly matched → true.

  • If not empty, there are unmatched opening brackets → false.

We can also simplify checking by mapping closing → opening:

  • ')' -> '('

  • ']' -> '['

  • '}' -> '{'


Algorithm (Step-by-Step):


  1. Initialize an empty stack.

  2. For each character c in s:

    • if c is an opening bracket:

      • Push it onto the stack.

    • else (it’s a closing bracket):

      • if the stack is empty → return false.

      • Pop the top element from the stack.

      • If the popped element is not the correct matching opening bracket for c → return false.

  3. After processing all characters:

    • if the stack is empty → return true.

    • else → return false.


Pseudo-code:



Complexity:


Let n = |s|:

  • Time: O(n) (each char is pushed/popped at most once).

  • Space: O(n) in worst case (all opening brackets on stack).


4. Java code:



5. C code:



6. C++ code:



7. Python code:



8.JavaScript code:




Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more