[Parentheses][Stack] Valid Parentheses

1. Example

s= "()" = > valid
s= "()[]{}"=> valid
s= "(]"=> invalid
s= "([)]"=> invalid


2. Implementation
Q1: parentheses is a pair, How to pair?
A1: Every left parenthesis need a RIGHT parenthesis to pair
Q1: Put left parenthesis onto Stack, and RIGHT comes out?
A1: pop up left parenthesis if RIGHT in in the way, NEED same type of parenthesis
Q1: is there any chance a type of parenthesis's RIGHT one occur very very late?
A1: POSSIBLE, but when that happen, no other parenthesis on top of it, meaning ALL OTHER PARENTHESES MUST HAVE BEEN PAIRED AND POPED OUT



// NOTE: BREAK, don't want to go over below cases

 break;
// NOTE: even equal, need to iterate instead of return 

if (stack.isEmpty() || stack.pop() != '(' ) return false; 

break;
default: break;

// NOTE: Otherwise, FASLE 

 return false;

// Time:O(string length), Space:O(string length)
public boolean isValid(String s)
{




      
      // Validate the input 
      if (s== null || s.length == 0)
          //return false;
          // NOTE: empty is always VALID pair
          return true





      LinkedList stack = new LinkedList();
      for (int i = 0 ; i < s.length(); i++) 
      {
           char c = s.charAt(i);
           switch(c)
           {
                case '(':
                case '[':
                case '{':
                    stack.push(c);
                    // NOTE: BREAK, don't want to go over below cases
                    break;
                case ')': 
                    //if (!stack.isEmpty())
                    //{
                    //    //char c2 = stack.pop();
                    //    // NOTE: Character
                    //    Character c2 = stack.pop();
                    //    // NOTE: Character equal http://www.tutorialspoint.com/java/lang/character_equals.htm
                    //    //return c2=='(';
                    //    return c2.equals('(');
                    //}
                    //else
                    //    return false;
                    // NOTE: even equal, need to iterate instead of return
                    if (stack.isEmpty() || stack.pop() != '(' )
                          return false;
                    break;
                case ']':
                    //if (!stack.isEmpty())
                    //{
                    //    //char c2 = stack.pop();
                    //    // NOTE: Character
                    //    Character c2 = stack.pop();
                    //    return c2=='[';
                    //    
                    //}
                    //else 
                    //    return false;
                    if ( stack.isEmpty() || stack.pop() != '[' )
                          return false;
                    break;
                case '}':
                    //if (!stack.isEmpty())
                    //{
                    //   Character c2 = stack.pop();
                    //    return c2 == '{';
                    //}
                    //else 
                    //    return false;
                    if (stack.isEmpty() || stack.pop() != '{')
                          return false;
                    break;
                default:
                    break;
           }
      }

 



      if (stack.isEmpty())
         return true;





      // NOTE: Otherwise, FASLE
      return false;



       
}

3. Similar Ones
(M) Generate Parentheses
(H) Longest Valid Parentheses