Valid Parentheses

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 '()[]{}'.

Functional Implementation of WordPattern

Java

  public boolean isValid1(String s) {
      char[] stack = new char[s.length()];
      int si = -1;
      for (int i = 0; i != s.length(); ++i) {
          switch (s.charAt(i)) {
              case '(':
                  stack[++si] = ')';
                  break;
              case '{':
                  stack[++si] = '}';
                  break;
              case '[':
                  stack[++si] = ']';
                  break;
              default:
                  if (si == -1 || stack[si] != s.charAt(i))
                      return false;
                  --si;
          }
      }
      return si == -1;
  }

Java

  public boolean isValid2(String s) {
      Stack<Character> a = new Stack<>();
      for (int i = 0; i < s.length(); i++) {
          char c = s.charAt(i);
          if ("({[".indexOf(c) >= 0)
              a.push(c);
          else {
              if (a.size() == 0)
                  return false;
              else {
                  char d = (char) a.pop();
                  if (c == ')' && d != '(')
                      return false;
                  else if (c == '}' && d != '{')
                      return false;
                  else if (c == ']' && d != '[')
                      return false;
              }
          }
      }
      if (a.size() != 0)
          return false;
      return true;
  }

See also :

Linear Search
Jump Search
Binary Search
Exponential Search
Interpolation Search