MongoDB

www.mongodb.com

Interview Question

Software Engineering Intern Interview

Given a set of open and close parenthesis, make sure the

  string is valid, such that each open parenthesis has a matching close parenthesis in the correct place.
Answer

Interview Answer

2 Answers

0

Use a stack - push on an open bracket, pop on a close bracket, and if a pop fails (due to an empty stack) then the string is invalid.

int on Oct 7, 2013
0

import java.util.*;
public class validString {
    public static boolean isValid(String str) {
        Set<Character> set = new HashSet<>();
        set.add('(');
        set.add('[');
        set.add('{');
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        str = str.replaceAll("\\s", "");
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            if (set.contains(str.charAt(i))) {
                stack.push(str.charAt(i));
            } else {
                if (stack.empty()) return false;
                char c = stack.pop();
                if (map.get(str.charAt(i)) != c) return false;
            }

        }
        return stack.empty();
    }
}

Anonymous on Sep 12, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.