Home | Projects | Notes > Problem Solving > LC - E - 20. Valid Parentheses (stack, map)

LC - E - 20. Valid Parentheses (stack, map)

Solutions in C++

Solution 1

This solution uses STL stack, and map container.

Complexity Analysis:

• $T=O(n)$$T = O(n)$ where $n$$n$ is the length of the given string s

• $S=O(n)$$S = O(n)$ as additional memory space is used for stack and map container

Solution:

xxxxxxxxxx
19
1
class Solution {
2
public:
3
    bool isValid(string s) {
4
        stack<char> st;
5
        map<char, char> m = { {'(', ')'}, {'{', '}'}, {'[', ']'} };        
6
    
7
        st.push(s[0]); // since s contains at least one character by the constraints
8

9
        for (int i = 1; i < s.size(); i++)
10
        {
11
            if (!st.empty() && m[st.top()] == s[i])
12
                st.pop();
13
            else
14
                st.push(s[i]);
15
        }       
16
        
17
        return st.empty();
18
    }
19
};

Solution 2

This solution uses STL stack, and map container.

Complexity Analysis:

• $T=O(n)$$T = O(n)$ where $n$$n$ is the length of the given string s

• $S=O(n)$$S = O(n)$ as additional memory space is used for stack and map container

Solution:

xxxxxxxxxx
21
1
class Solution {
2
public:
3
    bool isValid(string s) {
4
        stack<char> st;
5
        map<char, char> m = { {'(', ')'}, {'{', '}'}, {'[', ']'} };     
6

7
        for (auto ch : s)
8
        {
9
            // if open parenthesis
10
            if (ch == '(' || ch == '{' || ch == '[')
11
                st.push(ch);
12
            // if closing parenthesis 
13
            else if (!st.empty() && m[st.top()] == ch)
14
                st.pop();
15
            else
16
                return false;
17
        }
18
        
19
        return st.empty();  // cannot be 'return true' as it cannot catch "[" like case
20
    }
21
};