[CSE] 10.14

1. 括号匹配
给定一堆括号序列，请判断是不是合法的括号序列
()合法
(() 不合法
(())()合法

分析空间和时间

2.
Scramble with Friends是一款老少咸宜的益智类游戏 (下载地址：Apple Store  Google Play)
玩法是，给定一个4x4的方块矩阵，每个格子上都有一个字母。玩家需要来通过串连这些邻接（上，下，左，右，左上，左下，右上，右下）的方块组合成合法的单词（如上图的scrumble）。在规定时间内，找出的单词越多越好。（Please ignore the number on the tiles)

假如聪明的小伙伴你，是这个游戏的开发者。我们随机给你生成了一个nxn的字母矩阵，我们还给你一本单词本，里面列举了所有合法的英语词语（assume不多不少，）。你的任务是写一个程序找出这个矩阵可能出现的所有合法单词。

java:
String[] solve(char[][] matrix, String[] DanCiBook){
    //you code starts here.
} 

Time Limits : 1s (just kidding, i dont have OJ for this)
样例输入：
matrix:
[[o c],
 [b a]]
DanCiBook:
[cao, condom, cab, sexy, apple, fuck, cnm, nmb, cnmb, renjianbuchai, xidapuben,xiao, kan, shi, ge, da, sha, bi]
样例输出:  按alphabetic排序
  [cab, cao] 

[Solution].java

//1
public class Solution {
    public boolean validateParenthesis(String p) {
        if(p == null) return false;
    	int left = 0;
    	for(int i = 0; i < p.length(); i++){
    		if(p.charAt(i) == '(') left++;
    		else if(p.charAt(i) == ')') left--;
    		if(left < 0) return false;
    	}
    	return left == 0;
    }
}

//2