﻿namespace AlgoDS.Leetcode
{
    using System;
    using System.Collections.Generic;

    /// <summary>
    /// [[Problem]]
    /// Given a string 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.  Note that an empty string is also considered valid.
    /// [[Example]]
    /// Input: "(]"
    /// Output: false
    /// Input: "{[]}"
    /// Output: true
    /// </summary>
    public sealed class _20 : IOnlineProblem
    {
        public bool IsValid(string s)
        {
            if (s.Length == 0)
            {
                return true;
            }

            Stack<char> result = new Stack<char>();
            Dictionary<char, char> pars = new Dictionary<char, char>
            {
                {')','('},
                {']','['},
                {'}','{'}
            };

            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == '(' || s[i] == '{' || s[i] == '[')
                {
                    result.Push(s[i]);
                }
                else if (pars.ContainsKey(s[i]))
                {
                    if (result.Count == 0)
                    {
                        return false;
                    }
                    else if (result.Pop() != pars[s[i]])
                    {
                        return false;
                    }
                }
                else
                {
                    continue;
                }
            }

            return result.Count == 0;
        }

        public void Solve()
        {
            Console.WriteLine(IsValid(@"{[]}"));
        }
    }
}
