Leetcode_20_Valid Parentheses

本文是在学习中的总结,欢迎转载但请注明出处:http://blog.csdn.net/pistolove/article/details/41450987

通过本文你能学到如下知识:

(1)对数据结构中栈的理解,特别是Stack类中的peek()方法和pop()方法的区别。

(2)理解解题思路,提高思考问题的能力。

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.

题意:给定包含三种括号的字符串,判断该字符串中括号是否正确匹配。

解题思路:

(1)通过题意可知,括号是夹杂在字符之间的,而我们需要处理的是括号,所以,第一步是如何地将括号从字符串中分离出来。通过遍历字符串可将出现的括号存储起来。

(2)由于括号是成对进行匹配的,这里将成对出现的括号存储在HashMap中,以供后续查询比较。

(3)我们是通过一个栈来进行括号匹配的,我们将(1)中得到的括号往栈中存储以进行比较,第一个括号存储进去后,当第二个括号进入时需要进行判断。首先,判断其是否为

朝向左边的括号,这里用leftList.contains()进行判断,如果是不朝向左边的括号,将该括号压入栈中;如果不是朝向左边的括号,就需要从栈中取出元素和该括号进行比较,这里

用peep()方法获取当前的栈顶元素(不移除该元素)。其次,通过(2)中已获取的Map来得到与当前括号匹配的括号,如果得到的括号正好匹配,则从当前栈中移除已有元素,移

除栈顶元素的方法为pop();如果得到的括号不匹配,则匹配失败,返回false。最后,依次类推,直到所有的括号都进行匹配判断为为止。

PS:上面的解题思路肯定不是最好的,但其是本人自己思考的结果,虽然代码很罗嗦,但是思路还是比较清晰的,希望对你有所帮助,同时希望你给出建议,也希望能和大神进行一些交流。

解题代码如下(PS:本人技术比较菜,写的代码也很菜,但是OJ还是完全可以通过,大家有比较好的思路希望能够分享,谢谢):

public boolean isValid(String s) {
        int len = s.length();
		boolean isvalid = true;
		Stack<Character> stack = new Stack<Character>();
		Character[] all = {'[','(','{',']',')','}'};
		Character[] left = {']',')','}'};
		List<Character> leftlist = Arrays.asList(left);
		List<Character> alllist = Arrays.asList(all);

		Map<Character, Character> map = new HashMap<Character, Character>();
		map.put('[', ']');
		map.put('(', ')');
		map.put('{', '}');
		map.put('}', '{');
		map.put(')', '(');
		map.put(']', '[');

		LinkedList<Character> linked = new LinkedList<Character>();
		for (int i = 0; i < len; i++) {
			if(alllist.contains(s.charAt(i))){
				linked.add(s.charAt(i));
			}
		}

		if(linked.size()==0) return  true;
		stack.push(linked.get(0));

		for (int i = 1; i < linked.size(); i++) {
			Character str = linked.get(i);
			if(leftlist.contains(str) && stack.size() > 0){
				if(map.get(str).equals(stack.peek())){
					stack.pop();
				}else{
					isvalid = false;
				}
			}else{
				stack.push(str);
			}
		}

		if(stack!=null && stack.size()>0){
			isvalid = false;
		}

		return isvalid;
    }
上一篇:pytest 3.fixture介绍一 conftest.py


下一篇:EF 存储过程(下)