力扣 有效的括号 栈

Problem: 20. 有效的括号

文章目录

• 思路
• 复杂度
• 💝 Code

思路

👨‍🏫 参考地址

复杂度

时间复杂度:

O

(

n

)

O(n)

O(n)

空间复杂度:

O

(

n

)

O(n)

O(n)

💝 Code

class Solution {
	static Map map = new HashMap();
	static
	{
		map.put('(', ')');
		map.put('[', ']');
		map.put('{', '}');
//		map.put('?', '?');// 占位符
	}

	public boolean isValid(String s)
	{
		int n = s.length();
		if (n > 0 && !map.containsKey(s.charAt(0)))
			return false;
		LinkedList stack = new LinkedList();
		stack.add('?');
		for (Character c : s.toCharArray())
		{
			if (map.containsKey(c))
				stack.addLast(c);
			else if (map.get(stack.removeLast()) != c)
				return false;
		}
		return stack.size() == 1;// 合法的括号序列最后只剩下一个占位符 ？
	}
}