Interview Question Valid Parentheses

By Fatih KABAKCI

The problem is to find out if the input are composed by valid parentheses. The opening and closing brackets must be closed in the correct way.

Problem #20 - Valid Parentheses

Description: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Difficulty: Easy

Solution in Java

package com.fatihkabakci.Easy.ValidParentheses;

import java.util.LinkedList;

/**
 * @author fkabakci
 * 
 * Problem Description: Given a string containing just the characters "(", ")", "{", "}", "[" and "]", 
 * determine if the input string is valid. The brackets must close in the correct order, 
 * "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
 * 
 * Solution:
 * 
 * Go to first closing bracket, check whether the previous one is the correct opening tag. If so, remove those characters from the list,
 * until the list is empty.
 * 
 * 1. Put all characters to a collection list.
 * 2. While i : 0 to size of list
 * 	  if the character is one of the closing brackets - ")", "}", "]"
 * 		 a. Find out the conjugate one - "(", "{", "["
 * 		 b. Get the just previous character of current i in the list.
 * 		 c. Check them out if they are equal
 * 		 d. Remove both characters from the list.
 * 3. At the end, list should be empty if the matches are valid.
 */

public class ValidParentheses {
	public char conjugate(char c) {
		if (c == ")")
			return "(";
		else if (c == "]")
			return "[";
		else
			return "{";
	}

	public boolean isValid(String s) {
		LinkedList<Character> o = new LinkedList<Character>();
		for (char bracket : s.toCharArray()) {
			o.add(bracket);
		}

		int i = 0;
		while (i < o.size()) {
			char c = o.get(i);
			if (c == ")" || c == "}" || c == "]") {
				char _c = conjugate(c);
				char pc = (i > 0) ? o.get(i - 1) : "\0";
				if (pc != _c)
					return false;
				o.remove(i);
				o.remove(i - 1);
				i = i - 2;
			}
			i++;
		}
		return o.isEmpty();
	}

	public static void main(String[] args) {
		ValidParentheses v = new ValidParentheses();
		System.out.println(v.isValid("]"));
	}
}