zenefits电面 stringmatch正确解法

面试官给我出了道老题， 我用了一亩三分地上的dp解答，挂了；来源如下
1point3acres*com/bbs/thread-145290-2-1*html   (无权限加URL, 请自己把*换成.)
massivealgorithms*blogspot.com/2015/11/zenefits-interview-count-of-possible_28*html   (无权限加URL, 请自己把*换成.)
题目如下：
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc"
String s2 = "a+b+c-";

s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有四个。
结果测试sln.findMatches("aaaaaa", "a+a-") ，出来结果为0，sln.findMatches("aabbaaaa", "a+a-") ，出来结果还为0，不对，挂了

mitbbs上大牛们给出正确解答，包括dp解答，整理如下(麻烦给大米)：
1. dp
private String getToken(char c, char op) {
   String s = c + "" + c;
   if (op == '+')
      return s;
   return s + s;
}

private boolean match(String s1, int s1EndIndex, String token) {
   for (int i = token.length() - 1; i >= 0; i--, s1EndIndex--) {
      if (s1EndIndex < 0)
         return false;
            
      if (s1.charAt(s1EndIndex) != token.charAt(i))
         return false;
   }

   return true;
}
   
public int findMatches(String s1, String s2) {
   int s1Len = s1.length();
   int s2Len = s2.length() / 2;
        
   // 'results[i][j]' stores the number of matches of first 'j + 1' tokens
   // from 's2' in sub-string of s1: 's1[0, i]'.
   int[][] results = new int[s1Len][s2Len];
        
   for (int i = 0; i < s1Len; i++) {
      for (int j = 0; j < s2Len; j++) {
         if (i == 0) {
            results[i][j] = 0;

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
font>
        char character = s2.charAt(0);
        char op = s2.charAt(1);
        String s2Token = getToken(character, op);
        String s2WithoutCurToken = s2.substring(2);
        
        int result = 0;
        
        if (s1.startsWith(s2Token, begin)) {
            result += findMatches(s1, s2WithoutCurToken, begin + s2Token.
length(), cache);
        }
        result += findMatches(s1, s2, begin + 1, cache);
        
        cache.put(cacheKey, result);
        return result;
    }
   
    public int findMatches(String s1, String s2) {
        HashMap<String, Integer> cache = new HashMap<>();
        return findMatches(s1, s2, 0 /*begin*/, cache);
    }

JermaineDing 发表于 2016-2-18 05:59
楼主你好，那个recursive方法里面“String cacheKey = s2 + "_" + begin;. ”，为什么给cacheKey加下划线和 ...

我的理解 只是用来产生一个 unique key的，随你

楼主你好，那个recursive方法里面“String cacheKey = s2 + "_" + begin;. ”，为什么给cacheKey加下划线和begin？

LZ, py版本的有误， +=p*2 和 += p*4应该是 p[i]，不是p