找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1434|回复: 4
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Valid Parentheses】【刷题第一弹2014】

[复制链接]

7

主题

3

精华

195

积分

资深会员

Rank: 2

积分
195
发表于 10-22-2014 01:08 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 qiuchen 于 10-22-2014 01:36 AM 编辑

LeetCode – Valid Parentheses

LeetCode 通道:https://oj.leetcode.com/problems/valid-parentheses/
汇总帖子:http://www.meetqun.com/thread-703-1-1.html


问题: 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.

解题思路分析: 经典的栈匹配。创建一个栈,让左符号入栈,右符号出栈,并且检查栈是否为空. 时空复杂度都是O(n).

Java Solution:
  1. public static boolean isValid(String s) {
  2.    char[] charArray = s.toCharArray();

  3.    HashMap<Character, Character> map = new HashMap<Character, Character>();
  4.    map.put('(', ')');
  5.    map.put('[', ']');
  6.    map.put('{', '}');

  7.    Stack<Character> stack = new Stack<Character>();

  8.    for (Character c : charArray) {
  9.        if (map.keySet().contains(c)) {
  10.            stack.push(c);
  11.          } else if (map.values().contains(c)) {
  12.                if (!stack.isEmpty() && map.get(stack.peek()) == c) {
  13.                     stack.pop();
  14.              } else {
  15.                  return false;
  16.                      }
  17.              }
  18.          }
  19.         return stack.isEmpty();
  20.    }
复制代码




本帖被以下淘专辑推荐:

7

主题

3

精华

195

积分

资深会员

Rank: 2

积分
195
 楼主| 发表于 10-22-2014 01:24 AM | 显示全部楼层
本帖最后由 qiuchen 于 10-22-2014 01:31 AM 编辑

还有个更多见的solution: 基本与一楼一致,就是不使用char array. 仅用charAt去操作string中的字符
  1. public static boolean isValid(String s) {
  2.         HashMap<Character, Character> map = new HashMap<Character, Character>();
  3.         map.put('(', ')');
  4.         map.put('[', ']');
  5.         map.put('{', '}');

  6.         Stack<Character> stack = new Stack<Character>();

  7.         for (int i = 0; i < s.length(); i++) {
  8.                 char curr = s.charAt(i);

  9.                 if (map.keySet().contains(curr)) {
  10.                         stack.push(curr);
  11.                 } else if (map.values().contains(curr)) {
  12.                         if (!stack.empty() && map.get(stack.peek()) == curr) {
  13.                                 stack.pop();
  14.                         } else {
  15.                                 return false;
  16.                         }
  17.                 }
  18.         }

  19.         return stack.empty();
  20. }
复制代码
回复 支持 反对

使用道具 举报

7

主题

3

精华

195

积分

资深会员

Rank: 2

积分
195
 楼主| 发表于 10-22-2014 10:59 PM | 显示全部楼层
本帖最后由 qiuchen 于 10-22-2014 11:03 PM 编辑

不小心多打了一层楼 不知如何删除 麻烦管理员帮忙删除 抱歉
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表