`

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;
}

 

  • 大小: 28.7 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics