LeetCode 20. Valid Parentheses

🧩 PROBLEM - LeetCode 20. Valid Parentheses

LINK: https://leetcode.com/problems/valid-parentheses/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.

Example.

[1]

Input: s = “([])”

Output: true

[2]

Input: s = “([)]”

Output: false

Constraints:

0 <= s.length <= $10^4$

s consists of parentheses only ‘()[]{}’.

---

Problem anaylsis

1. string type is just three pair of parentheses
2. The process should be locked and unlocked. matching systems.
3. length is 10,000, it is not big if time complex is under O(n) or O(n $\log{n}$)
4. bitmask or mapping is not good. mapping process should have O(n) and ASCII code is not regular.
5. Accumulation with process and checking hold and release.

Similar like STACK STRUCTURE

```cpp class Solution { public: bool isValid(string s) { bool bReturn = false;

        do
        {
            if (s.length() % 2 == 1)
                break;

            std::vector<char> vctContainer;
            char i8Recent = 0;

            if (s[0] == ']' ||
                s[0] == ')' ||
                s[0] == '}')
                break;

            bool bError = false;

            for (int i = 0; i < (int)s.length(); ++i)
            {
                char i8Current = s[i];
            
                if (i8Current == '[' ||
                    i8Current == '(' ||
                    i8Current == '{')
                {
                    vctContainer.push_back(i8Current);
                    i8Recent = i8Current;
                }
                else
                {
                    if (vctContainer.size() == 0)
                    {
                        bError = true;
                        break;
                    }

                    char i8Lastest = vctContainer.back();
                    bool bRelease = false;

                    if (i8Lastest == '[' && i8Current == ']')
                        bRelease = true;
                    else if (i8Lastest == '{' && i8Current == '}')
                        bRelease = true;
                    else if (i8Lastest == '(' && i8Current == ')')
                        bRelease = true;
                    else
                    {
                        bError = true;
                        break;
                    }
                    
                    if(bRelease)
                        vctContainer.pop_back();
                }
            }
                
            if (!bError && vctContainer.size() == 0)
                bReturn = true;
        } 
        while (false);

        return bReturn;
} }; ```

It is not using stack but stacking data and pop the data that it is satisfied with condition.

---

---

Anaylsis

• CHECK SCOPE -> INPUT SIZE
  • Under Hundred: O($2^n$)
  • Under thousand : O($n^2$)
  • Under 10K: O(N $\log{N}$)
  • Under 1M ~ over: O( $\log{n}$)
• COMPLEXITY
  • Time complexity
  • Space complexity
• Check Valid DataType
  • Overflow
• SIMULATION
  • Check test case by myself
• Compare with other people solutions

---

---