Zenefits Interview - Count of Possible Matches

String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷

s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有四个。

我们只考虑s1里的"aa"的情况，假设s1不会出现aaa或者aaaa的情况。(考官这个意思)

 

这题出的非常好！是一道动脑筋但是又考察面试者思路的题。看图解释。

 

public int possibleMatches(String txt, String pat) {
	String regex = pat.replace("+", "{2}.*?").replace("-", "{4}.*?");
	Matcher m = Pattern.compile(regex).matcher(txt);
	int matches = 0;
	while(m.find()) {
		matches++;
		System.out.println(m.group());
	}
	int size = pat.split("[\\+\\-]").length;
	int[][] f = new int[matches][size];
	Arrays.fill(f[0], 1);
	for(int i=0; i<matches; i++) {
		f[i][0] = 1;
	}
	for(int i=1; i<matches; i++) {
		for(int j=1; j<size; j++) {
			f[i][j] = f[i-1][j] + f[i][j-1];
		}
	}
	int sum = 0;
	for(int i=0; i<matches; i++) {
		sum += f[i][size-1];
	}
	return sum;
}