Zenefits Interview - Count of Possible Matches - - 博客频道 - CSDN.NET

Zenefits Interview - Count of Possible Matches - - 博客频道 - CSDN.NET
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;
}

http://www.1point3acres.com/bbs/thread-145290-1-1.html

1. public class Solution {
2.         public int findMatches(String s1, String s2){. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
3.        int len1 = s1.length(), len2 = s2.length();
4.        if (len2 > len1) return 0;
5.        if (len2 == 0 || len2 %2 != 0) return 0;
6.        // DP matches each pattern
7.        // number of matches between s1.substring(0, i + 1) and s2.substring(j * 2, j * 2 + 2). more info on 1point3acres.com
8.        int[][] dp = new int[len1 + 1][len2 / 2 + 1];
9.        // no match for dp[0][j]
10.        for (int i = 1; i < len1; i++){
11.            dp[i + 1][0] = 1;.1point3acres缃�
12.            for (int j = 0; j < len2 / 2; j++){
13.                dp[i + 1][j + 1] = dp[i][j + 1];
14.                if (isMatch(s1, s2, i, j)){
15.                    if (s2.charAt(2*j + 1) == '+'). 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
16.                        dp[i + 1][j + 1] += dp[i - 1][j];
17.                    else
18.                        dp[i + 1][j + 1] += dp[i - 3][j];
19.                }. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
20.            }
21.        }
22.        return dp[len1][len2 / 2];
23.    }
24. 
    
25.    boolean isMatch(String s1, String s2, int i, int j){
26.        char c = s2.charAt(j * 2);
27.        char p = s2.charAt(j * 2 + 1);
28.        int len = p == '+' ? 2 : 4;
29.        if (i - len < -1) return false;
30.        for (int h = i - len + 1; h <= i; h++){
31.            if (s1.charAt(h) != c) return false;
32.        }
33.        return true;
34.    }. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
35.    
36.    public static void main(String[] args){. Waral 鍗氬鏈夋洿澶氭枃绔�,
37.            Solution sln = new Solution();
38.            // 4. 鍥磋鎴戜滑@1point 3 acres
39.            System.out.println(sln.findMatches("waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c-"));
40.            // 5. Waral 鍗氬鏈夋洿澶氭枃绔�,
41.            System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-"));
42.    }
43. }

http://blog.csdn.net/yuanhisn/article/details/46118447

这种字符串匹配题，不难想到用DP或者recursion，与leetcode的115题结合，就可以做，但有几个地方需要注意：

1. 首先需要将s1和s2转化，s1要把关键字符提取出来，并且做变换，变成"abcabc"，s2要把加减号去掉变成"abc"，然后再做。

2. 为什么不把这道题直接变成"aabbccccaabbcccc"和"aabbcccc"然后再做呢，为什么要变成单个字符的形式。这道题和LC 115题不一样的地方在于，比如"aaaa"和"aa"，在LC的题目中，有6种匹配，而在这道题中，只有三种，因为这道题里必须连续。也就是说如果变成"aabbccccaabbcccc"和"aabbcccc" ，其实只有四种匹配方式，但实际我们用DP或者recursion的时候"aabbccccaabbcccc"和"aabbcccc"也可以匹配，就多算了很多种情况。

3. 所以如果单纯的变成"aabbccccaabbcccc"和"aabbcccc”再做是不行的。变成"abcabc"和"abc"是正道。

4. 如果s1出现“aaabbcccc” 三个a这种情况，怎么办？那么就把s1变成“aabc”，因为"aaa"中可以选前两个a也可以选后两个a，两种匹配方式。

Read full article from Zenefits Interview - Count of Possible Matches - - 博客频道 - CSDN.NET