对stack的定势思维

Posted on   |   In   |  

今天在codewar上做了这样一道题

In English and programming, groups can be made using symbols such as () and {} that change meaning. However, these groups must be closed in the correct order to maintain correct syntax.

Your job in this kata will be to make a program that checks a string for correct grouping. For instance, the following groups are done correctly:

({})
[]
[{()}]
The next are done incorrectly:

{(})
([]
[])

A correct string cannot close groups in the wrong order, open a group but fail to close it, or close a group before it is opened.

Your function will take an input string that may contain any of the symbols (), {} or [] to create groups.

It should return True if the string is empty or otherwise grouped correctly, or False if it is grouped incorrectly.

在我脑海中蹦出来的第一个想法就是使用栈来保存弹出，来判断括号是否匹配

我的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Groups {
    public static String left = "{[(";
    public static String right = "}])";

    public static boolean groupCheck(String s){
        if (s == null || s.length() == 0) {
            return true;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (left.contains(String.valueOf(s.charAt(i)))) {
                stack.push(s.charAt(i));
            } else if (!stack.empty()) {
                Character c = stack.pop();
                if (right.indexOf(s.charAt(i)) != left.indexOf(c)) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return stack.empty();
    }

    @Test
    public void myTests() {
        assertEquals(Groups.groupCheck("()"), true);
        assertEquals(Groups.groupCheck("({"), false);
    }
}

边写边想，写的比较随意。
提交之后发现了一个简单至极的方案，完全不需要用栈来实现

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Groups{
  public static boolean groupCheck(String s) {
    int len;
    do {
      len = s.length();
      s = s.replace("()", "");
      s = s.replace("{}", "");
      s = s.replace("[]", "");
    } while (len != s.length());
    return s.length() == 0;
  }
}

我看到之后想简直太厉害了，几行代码就实现了，还没有那么复杂的判断，关键是纯String操作。
优雅！

我们的头脑遇到问题时会搜索一下有没有现成的解决方案，这在一定程度上减少了我们的脑力浪费，
但也有可能让我们丧失了创新的可能。遇事何不先问下自己还有其他的解决方案么？