Fuck LeetCode  >  Stack and Queue  >  20. Valid Parentheses  >  Solved in JavaScript, Python, Java, C++, C#, Go, Ruby  >  Repost or Contribute

    LeetCode link: 20. Valid Parentheses, difficulty: Easy.

    Given a string s containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

    An input string is valid if:

    1. Open brackets must be closed by the same type of brackets.
    2. Open brackets must be closed in the correct order.
    3. Every close bracket has a corresponding open bracket of the same type.

    Example 1:

    Input: s = "()"

    Output: true

    Example 2:

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

    Output: true

    Example 3:

    Input: s = "(]"

    Output: false

    Example 4:

    Input: s = "([])"

    Output: true

    Constraints:

    • 1 <= s.length <= 10000
    • s consists of parentheses only ()[]{}.
    Hint 1

    Use a stack of characters.

    Hint 2

    When you encounter an opening bracket, push it to the top of the stack.

    Hint 3

    When you encounter a closing bracket, check if the top of the stack was the opening for it. If yes, pop it from the stack. Otherwise, return false.

    Intuition
    PreviousNext

    1. Bracket matching focuses on the previous character and the current character. There are two situations to consider:
      1. If the current character is a left bracket, there is no need to match it and it can be saved directly.
      2. If the current character is a right bracket, and the previous character and the current character are paired, both characters can disappear; otherwise, if the pairing fails, false is returned directly.
    2. This scenario that focuses on the previous character and the current character is suitable for implementation with a stack.
    3. The mapping relationship between left and right brackets can be saved in a Map.
    4. Finally, if the stack is empty, it means that all pairings are successful and true is returned; otherwise, false is returned.

    Complexity

    Time complexity

    O(N)

    Space complexity

    O(N)

    Solution in languages: JavaScript Python Java C++ C# Go Ruby

    JavaScript # 

    /**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  const closeToOpen = new Map([
    [')', '('],
    ['}', '{'],
    [']', '['],
  ])
  const stack = []

  for (const char of s) {
    if (!closeToOpen.has(char)) {
        // is open bracket
        stack.push(char)
        continue
    }
    // is close bracket

    if (stack.length === 0) {
        return false
    }

    // stack top value doesn't match the expected value
    if (stack.pop() != closeToOpen.get(char)) {
        return false
    }
  }

  return stack.length === 0
};

    Python # 

    class Solution:
    def isValid(self, s: str) -> bool:
        # Map closing brackets to their opening brackets
        close_to_open = {
            ')': '(',
            '}': '{',
            ']': '[',
        }
        stack = []

        for char in s:
            if char not in close_to_open:
                # is open bracket
                stack.append(char)
                continue
            # is close bracket

            if not stack:
                return False

            # stack top value doesn't match the expected value
            if stack.pop() != close_to_open[char]:
                return False

        return not stack

    Java # 

    class Solution {
    public boolean isValid(String s) {
        // Map closing brackets to their opening brackets
        var closeToOpen = new HashMap<Character, Character>();
        closeToOpen.put(')', '(');
        closeToOpen.put('}', '{');
        closeToOpen.put(']', '[');

        var stack = new Stack<Character>();

        for (char c : s.toCharArray()) {
            if (!closeToOpen.containsKey(c)) {
                // is open bracket
                stack.push(c);
                continue;
            }
            // is close bracket

            if (stack.isEmpty()) {
                return false;
            }

            // stack top value doesn't match the expected value
            if (stack.pop() != closeToOpen.get(c)) {
                return false;
            }
        }

        return stack.isEmpty();
    }
}

    C++ # 

    class Solution {
public:
    bool isValid(string s) {
        // Map closing brackets to their opening brackets
        unordered_map<char, char> closeToOpen = {
            {')', '('},
            {'}', '{'},
            {']', '['}
        };

        stack<char> st;

        for (char c : s) {
            if (closeToOpen.find(c) == closeToOpen.end()) {
                // is open bracket
                st.push(c);
                continue;
            }
            // is close bracket

            if (st.empty()) {
                return false;
            }

            // stack top value doesn't match the expected value
            if (st.top() != closeToOpen[c]) {
                return false;
            }

            st.pop();
        }

        return st.empty();
    }
};

    C# # 

    public class Solution
{
    public bool IsValid(string s)
    {
        // Map closing brackets to their opening brackets
        var closeToOpen = new Dictionary<char, char>()
        {
            {')', '('},
            {'}', '{'},
            {']', '['}
        };

        var stack = new Stack<char>();

        foreach (char c in s) {
            if (!closeToOpen.ContainsKey(c))
            {
                // is open bracket
                stack.Push(c);
                continue;
            }
            // is close bracket

            if (stack.Count == 0)
            {
                return false;
            }

            // stack top value doesn't match the expected value
            if (stack.Pop() != closeToOpen[c])
            {
                return false;
            }
        }

        return stack.Count == 0;
    }
}

    Go # 

    func isValid(s string) bool {
    // Map closing brackets to their opening brackets
    closeToOpen := map[rune]rune{
        ')': '(',
        '}': '{',
        ']': '[',
    }

    stack := []rune{}

    for _, char := range s {
        if _, isClose := closeToOpen[char]; !isClose {
            // is open bracket
            stack = append(stack, char)
            continue
        }
        // is close bracket

        if len(stack) == 0 {
            return false
        }

        lastChar := stack[len(stack) - 1]

        // stack top value doesn't match the expected value
        if lastChar != closeToOpen[char] {
            return false
        }

        stack = stack[:len(stack) - 1] // pop operation
    }

    return len(stack) == 0
}

    Ruby # 

    # @param {String} s
# @return {Boolean}
def is_valid(s)
  # Map closing brackets to their opening brackets
  close_to_open = {
    ')' => '(',
    '}' => '{',
    ']' => '['
  }

  stack = []

  s.each_char do |char|
    if !close_to_open.key?(char)
      # is open bracket
      stack.push(char)
      next
    end
    # is close bracket

    if stack.empty?
      return false
    end

    # stack top value doesn't match the expected value
    if stack.pop != close_to_open[char]
      return false
    end
  end

  stack.empty?
end
    Solution in languages: JavaScript Python Java C++ C# Go Ruby

    Other languages

    Welcome to contribute code to our GitHub repository, thanks! The location of this solution is 20. Valid Parentheses.
    PreviousNext