[LeetCode] 20. Valid Parentheses (C#)

LeetCode - Problems - Algorithms - 20. 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.

Example 1:

• Input: s = "()"
• Output: true

Example 2:

• Input: s = "()[]{}"
• Output: true

Example 3:

• Input: s = "(]"
• Output: false

Example 4:

• Input: s = "([)]"
• Output: false 

Example 5:

• Input: s = "{[]}"
• Output: true 

Constraints:

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

2019년 12월 수많은 시도들.. 그리고 포기

이 문제는 재작년 12월에 LeetCode를 처음 접했을 때, 너무 어려워서 포기했었다.

당시에는 배우적 없는 해시테이블, 스택 등을 이용하라고 하고 이미지로 깔끔하게 설명되어서 이해는 됬는데 코드를 봐도 이해가 안되어서 포기하고 넘겼었다.

그리고 이 문제를 끝으로 LeetCode와 멀어졌다.... (숙연)

이제 스택도 쓸 줄 알겠다, 드디어 풀 수 있겠군! 하고 들어갔는데 스택을 사용하지 않아도 간단하게 풀 수 있는 방법을 찾아냈다.

My Solution (C#) 

public class Solution {
        public bool IsValid(string s)
        {
            string[] validSet = { "[]", "{}", "()" };

            while (s.Contains("[]") || s.Contains("{}") || s.Contains("()"))
            {
                s = s.Replace(validSet[0], "");
                s = s.Replace(validSet[1], "");
                s = s.Replace(validSet[2], "");
            }

            if (s == "")
            {
                return true;
            }
            else
            {
                return false;
            }
        }
}

또는, (아래 더보기 클릭)

{
            bool checker = true;
            while (checker)
            {
                if (s.Contains("[]"))
                {
                    s = s.Replace("[]", "");
                }
                else if (s.Contains("{}"))
                {
                    s = s.Replace("{}", "");
                }
                else if (s.Contains("()"))
                {
                    s = s.Replace("()", "");
                }
                else
                {
                    checker = false;
                }
            }

            if (s == "")
            {
                return true;
            }
            else
            {
                return false;
            }
        }

아주 간단하게 Containds와 Replace 메소드들을 이용하면 된다.

다만 효율은 그리 좋지 않다.

 

• s consists of parentheses only '()[]{}'.

라는 말은 즉, ()[]{} 외의 값은 포함하지 않으며, 따라서 유효한 set는 무조건 붙어있게 된다.

즉 s 값 안에 contains method를 이용해 "()", "[]", "{}" 값이 있는지 확인하고,

존재하는 "()"와 "[]", "{}" 값을 모두 "" 빈 string 값으로 replace 반복 해주면 된다.

 

결과를 보면 다른 C# 솔루션에 비해 현저히 느린 속도임을 알 수 있다.

Contains와 Replace method는 주어진 Array 혹은 String 값을 처음부터 끝까지 전부 훑어보기 때문에 time complexity는 O(n)이 된다. 반복문 한번에 이를 O(6n) 실행하므로 최악의 경우 O((s.Length/2) * 6 * n)이 되는 셈이다. 

반면에 Stack을 이용하게 되면 주어진 String 값을 처음부터 끝까지 혹은 Invalid 하다면 중간까지만 체크하므로 최악의 경우가 O(n)이니 훨씬 빠를 수 밖에 없다.

내일은 Stack을 이용해서 풀어봐야지.

 

LeetCode - 20. Valid Parentheses

++추가

My Solution (C#) - Using Stack

public class Solution {
    public bool IsValid(string s)
    {
            if ( string.IsNullOrWhiteSpace(s) )
            {
                return false;
            }

            Stack<char> myStack = new Stack<char>();

            Dictionary<char, char> validSet = new Dictionary<char, char>();
            validSet.Add('{', '}');
            validSet.Add('[', ']');
            validSet.Add('(', ')');

            foreach (char l in s)
            {
                if (validSet.ContainsKey(l)) //(validSet.ContainsKey(l))
                {
                    myStack.Push(l);
                }
                else //not 0 // if (validSet.ContainsValue(l))
                {
                    if (myStack.Count != 0 && validSet[myStack.Peek()] == l)
                        myStack.Pop();
                    else
                        return false;
                }
            }

            return myStack.Count == 0 ? true : false;
    }
}

스택을 이용한 풀이법.

Dictionary validSet을 정의하고 그 안에 opening parentheses를 key로, closing parentheses를 value로 맞춰 넣는다.

주어진 string s 안에 있는 char l을 모두 확인하기 위한 foreach 반복문을 열어주고

 > 만약 그 안에 l이 key로서 존재하는 지 확인 한 뒤, 존재한다면 l을 myStack에 쌓아준다.

 > 아니라면 l은 무조건 closing parentheses이므로

   >myStack이 0이 아니고(&&) 마지막에 myStack에 쌓인 값을 Key로하는 value가 l인지 확인 한 뒤 myStack의 마지막 값을 pop 해준다.

   > 0이거나 맞는 value가 아닌 경우 invalid parentheses이므로 false를 바로 리턴해준다.

foreach 반복문이 끝났을 때 myStack에 남아있는 값이 있는지 체크하고 없다면 true, 있다면 false를 리턴한다. 

 

ContainsKey O(1)이고, Stack의 insert(push)와 delete(pop) 또한 각각 O(1)이므로 위 솔루션의 time coplexity는 O(n)이 된다.

LeetCode - 20. Valid Parentheses - Using Stack