Posts Valid Parentheses
Post
Cancel

Valid Parentheses

PROBLEM DESCRIPTION

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

An input string is valid if:

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

leetcode

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {

    public boolean isValid(String s) {

        int n = s.length();

        // Create a mapping of closing brackets to their corresponding opening brackets.
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        // Set to store the open brackets.
        Set<Character> openBrackets = new HashSet<>();
        openBrackets.add('(');
        openBrackets.add('{');
        openBrackets.add('[');

        // Create a stack to keep track of the brackets.
        Stack<Character> stack = new Stack<>();

        // Iterate through each character in the string.
        for (int i = 0; i < n; i++) {

            Character c = s.charAt(i);

            // If the current character is an open bracket, push it onto the stack.
            if (openBrackets.contains(c)) {
                stack.push(c);
            // If will be a close bracket
            } else {

                // If the stack is empty, there's no corresponding open bracket, so the string is invalid.
                if (stack.isEmpty()) {
                    return false;
                }

                // Check if the current closing bracket matches the one at the top of the stack.
                if (stack.peek() == map.get(c)) {
                    stack.pop(); // Pop the open bracket from the stack to remove this matched pair
                } else {
                    return false; // If there's a mismatch, the string is invalid.
                }

            }

        }

        // If the stack is empty, all brackets were matched and popped, so the string is valid.
        return stack.isEmpty();
    }
}

ANOTHER WAY TO CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {

    public boolean isValid(String s) {

        Map<Character, Character> map = new HashMap<>();

        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        int n = s.length();

        Stack<Character> stack = new Stack<>();

        for(int i=0; i<n; i++){

            char ch = s.charAt(i);

            // if it's not a closing bracket, push to stack
            if(!map.containsKey(ch)){
                stack.push(ch);

            // current char is a closing bracket
            // so, there must corresponding open bracket in the stack at the top
            }else{

                // if stack is empty, return false
                if(stack.isEmpty())
                    return false;

                // check if the right closing bracket is at the top of the stack
                // if not, return false
                if(stack.pop() != map.get(ch))
                    return false;

            }

        }

        // finally, the stack should be empty for a valid string
        return stack.isEmpty();

    }

}
This post is licensed under CC BY 4.0 by the author.