面试官给我出了道老题, 我用了一亩三分地上的dp解答,来源如下
http://www.1point3acres.com/bbs/thread-145290-1-1.html
题目如下:
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,不对,挂了
另外System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")); 跑出来是5,感觉正确结果应该是2
不知道用dp正确的解答应该是什么?有人能给出正确的dp代码吗?
以下是从拷贝的测试用例不通过的代码:
public class Solution {
public int findMatches(String s1, String s2){
int len1 = s1.length(), len2 = s2.length();
if (len2 > len1) return 0;
if (len2 == 0 || len2 %2 != 0) return 0;
// DP matches each pattern
// number of matches between s1.substring(0, i + 1) and s2.substring(j * 2, j * 2 + 2)
int[][] dp = new int[len1 + 1][len2 / 2 + 1];
// no match for dp[0][j]
for (int i = 1; i < len1; i++){
dp[i + 1][0] = 1;
for (int j = 0; j < len2 / 2; j++){
dp[i + 1][j + 1] = dp[i][j + 1];
if (isMatch(s1, s2, i, j)){
if (s2.charAt(2*j + 1) == '+')
dp[i + 1][j + 1] += dp[i - 1][j];
else
dp[i + 1][j + 1] += dp[i - 3][j];
}
}
}
return dp[len1][len2 / 2];
}
boolean isMatch(String s1, String s2, int i, int j){
char c = s2.charAt(j * 2);
char p = s2.charAt(j * 2 + 1);
int len = p == '+' ? 2 : 4;
if (i - len < -1) return false;
for (int h = i - len + 1; h <= i; h++){
if (s1.charAt(h) != c) return false;
}
return true;
}
public static void main(String[] args){
Solution sln = new Solution();
System.out.println(sln.findMatches("waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c-")); // 4
System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")); // 5 ??? I think it should be 2
System.out.println(sln.findMatches("aaaaaa", "a+a-"));//0 wrong!
}
}