Dada una cadena que contiene solo los caracteres ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determina si la cadena de entrada es válida.
Los corchetes deben cerrarse en el orden correcto, «()» y «()[]{} «son todos válidos pero» (]»y» ([)]» no son.
Análisis
Un problema típico que se puede resolver utilizando una estructura de datos de pila.
Solución Java
public static boolean isValid(String s) { HashMap<Character, Character> map = new HashMap<Character, Character>(); map.put('(', ')'); map.put('[', ']'); map.put('{', '}'); Stack<Character> stack = new Stack<Character>(); for (int i = 0; i < s.length(); i++) { char curr = s.charAt(i); if (map.keySet().contains(curr)) { stack.push(curr); } else if (map.values().contains(curr)) { if (!stack.empty() && map.get(stack.peek()) == curr) { stack.pop(); } else { return false; } } } return stack.empty(); } |
