b*******g
发帖数: 36 | 1 题目如下：
String s1 = "
waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";
s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也
就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺
序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有
四个。
----------------------------------------------------------------------
这里有解答，但是测试后发现不对（http://www.1point3acres.com/bbs/thread-145290-1-1.html）
结果测试sln.findMatches("aaaaaa", "a+a-") ，出来结果为0，不对
另外System.out.println(sln.findMatches("
waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+
b+c+c-")); 跑出来是5，感觉正确结果应该是2
不知道用dp正确的解答应该是什么？有大牛能给出正确的解答吗？
以下是不正确的dp代码（http://www.1point3acres.com/bbs/thread-145290-1-1.html）：
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!
}
} |
p**r
发帖数: 5853 | 2 2p的变种版本
懒得写代码了，给个解题思路
abc
先ac两头往中间搜s=0,e=s1.Length-1
while(s
{
while(符合s2第一个字符)s++;aCount++;
while(符合s2最后一个字符)e--;cCount++;
if(aCount>amin&&cCount>cmin)
{
//开始日B
//日B的时候要注意必须在两腿(a位置+amin+1 and c位置-1)之间日
//才算是日对地方，不然就是爆菊，无效
}
}
符合ac最低标准后，再加入b搜索，一直到s>=e
处理s2的时候没space限制，
可以先把s2转换成hash
a+b+c-=a2/b2/c4
a+a-=a6 |
b*******g
发帖数: 36 | 3 谢谢你的思路，但是这是dynamic programming的版本吗？请问用dynamic programming
怎么做呢？ 上面 dynamic programming 的代码怎么改正呢？
这个跟leetcode中DistinctSubsequences有些像，但不全一样 |
p**r
发帖数: 5853 | 4 看过三分地的原题，没要求用DP，
如果用DP，感觉是大概这样思路：
先最简化问题：s1忽视所有invalid字符(扫描O(n)的时候直接忽略了)
s2=ab
1: ab=1
2: aab=a(ab)=ab+ab=2
3: abb=(ab)b=ab+ab=2
//2,3为同一个f
4: aabb=(a)ab(b)=aab+abb=4
然后再分析abc的情况
这里a可以是aa，aaa，aaaa
感觉这题用DP很累，分析半天，还是用我的吧，哈哈。
programming
【在 b*******g 的大作中提到】
: 谢谢你的思路，但是这是dynamic programming的版本吗？请问用dynamic programming
: 怎么做呢？ 上面 dynamic programming 的代码怎么改正呢？
: 这个跟leetcode中DistinctSubsequences有些像，但不全一样
|
p**r
发帖数: 5853 | 5 又想到一种很省脑子的解法
把s2做成stack,a+b+c-=abbcccc(去掉第一个字符)
建一个空的List>
int count=0;
然后s1 loop的时候
每次遇到s1[i]=s2[0]的时候
就加一个新的s2 stack到list里去
然后遇到s2中的任何字符就把list里所有的stack pop
当pop遇到null的时候就count++
最后return count
时间也是O(n)，空间就extra O(m*m)有点略坑爹，
但是没要求，这样比较省脑子，test的时候也不用考虑太多。
不用stack做，也可以用递归，同样道理
programming
【在 b*******g 的大作中提到】
: 谢谢你的思路，但是这是dynamic programming的版本吗？请问用dynamic programming
: 怎么做呢？ 上面 dynamic programming 的代码怎么改正呢？
: 这个跟leetcode中DistinctSubsequences有些像，但不全一样
|
s*******n
发帖数: 163 | 6 这题就是leetcode中DistinctSubsequences的变种。
先扩展S2，"a+b+c-"变成"aabbcccc"，然后就完全是DistinctSubsequences原题了。发
一个我公布在github上的DistinctSubsequences的DP解法： https://github.com/
vinceyuan/leetcode_solutions/tree/master/N115DistinctSubseq
可能我解释的不是很清楚，你把我给出的例子走一遍就清楚了。不清楚的地方再问我。 |
p**r
发帖数: 5853 | 7 这题为什么要DP解法？
space/time都是O(n2)啊
【在 s*******n 的大作中提到】
: 这题就是leetcode中DistinctSubsequences的变种。
: 先扩展S2，"a+b+c-"变成"aabbcccc"，然后就完全是DistinctSubsequences原题了。发
: 一个我公布在github上的DistinctSubsequences的DP解法： https://github.com/
: vinceyuan/leetcode_solutions/tree/master/N115DistinctSubseq
: 可能我解释的不是很清楚，你把我给出的例子走一遍就清楚了。不清楚的地方再问我。
|
p**r
发帖数: 5853 | 8 把代码里所有len2 / 2 + 1改成(len2+1)/2+1就可以了
programming
【在 b*******g 的大作中提到】
: 谢谢你的思路，但是这是dynamic programming的版本吗？请问用dynamic programming
: 怎么做呢？ 上面 dynamic programming 的代码怎么改正呢？
: 这个跟leetcode中DistinctSubsequences有些像，但不全一样
|
p**r
发帖数: 5853 | 9 这板块估计尽他妈的60，70后，
说起废话来一个比一个多，指点江山得不行，
一要实际解决点问题，都他妈的都哑巴了，
好好学学人家90后的技术论坛，
啥都愿意share，讨论氛围好多了。 |
h**********I
发帖数: 51 | 10
不对吧。
比如a+变成aa，这两个a是不能分开的。
【在 s*******n 的大作中提到】
: 这题就是leetcode中DistinctSubsequences的变种。
: 先扩展S2，"a+b+c-"变成"aabbcccc"，然后就完全是DistinctSubsequences原题了。发
: 一个我公布在github上的DistinctSubsequences的DP解法： https://github.com/
: vinceyuan/leetcode_solutions/tree/master/N115DistinctSubseq
: 可能我解释的不是很清楚，你把我给出的例子走一遍就清楚了。不清楚的地方再问我。
|
|
|
s*******n
发帖数: 163 | 11
为什么要用DP？因为leetcode上DistinctSubsequences这题我只会DP解法，没想到其他
方法。
准确的说space/time应该是O(n*m) n是s1的长度，m是s2的长度。
你的解法似乎有问题，比如s1是aabbb, s2是abb (不考虑楼主的题，只考虑leetcode上
DistinctSubsequences)，结果应该是6。
【在 p**r 的大作中提到】
: 这题为什么要DP解法？
: space/time都是O(n2)啊
|
h**********I
发帖数: 51 | 12 原题里的例子的答案确实是4.
2或者5都不对。LZ你再仔细看看。。
用眼睛看就能看出是4的。 |
h**********I
发帖数: 51 | 13 private String getToken(char c, char op) {
String s = c + "" + c;
if (op == '+')
return s;
return s + s;
}
private int findMatches(String s1, String s2, int begin, HashMap
Integer> cache) {
if (s2.length() == 0)
return 1;
if (begin >= s1.length() - 1)
return 0;
String cacheKey = s2 + "_" + begin;
if (cache.containsKey(cacheKey))
return cache.get(cacheKey);
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 cache = new HashMap<>();
return findMatches(s1, s2, 0 /*begin*/, cache);
} |
h**********I
发帖数: 51 | 14
LZ给的测试例子和原题里的有点不一样。
s1=waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc
s2=a+b+c+c-
的话，答案确实是5.
中间的cccc就可以拆成3个不同的答案了：
CC cc
c CC c
cc CC
1point3acres的代码貌似就是没有能handle例如"aaaaaa", "a+a-"的corner case。
【在 h**********I 的大作中提到】
: 原题里的例子的答案确实是4.
: 2或者5都不对。LZ你再仔细看看。。
: 用眼睛看就能看出是4的。
|
s*******n
发帖数: 163 | 15 哦，应该是你对。我被这句话误导了：“abc顺序不能变，但是之间可以有零个或多个
字符”
【在 h**********I 的大作中提到】
:
: LZ给的测试例子和原题里的有点不一样。
: s1=waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc
: s2=a+b+c+c-
: 的话，答案确实是5.
: 中间的cccc就可以拆成3个不同的答案了：
: CC cc
: c CC c
: cc CC
: 1point3acres的代码貌似就是没有能handle例如"aaaaaa", "a+a-"的corner case。
|
p**r
发帖数: 5853 | 16 你说的没错，我的DP解法有问题，
如果用DP解，应该是每个字符符合情况都基于前一个字符的情况做叠加。
【在 s*******n 的大作中提到】
: 哦，应该是你对。我被这句话误导了：“abc顺序不能变，但是之间可以有零个或多个
: 字符”
|
p**r
发帖数: 5853 | 17 楼主要的是DP解法
String,
【在 h**********I 的大作中提到】
:
: LZ给的测试例子和原题里的有点不一样。
: s1=waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc
: s2=a+b+c+c-
: 的话，答案确实是5.
: 中间的cccc就可以拆成3个不同的答案了：
: CC cc
: c CC c
: cc CC
: 1point3acres的代码貌似就是没有能handle例如"aaaaaa", "a+a-"的corner case。
|
h**********I
发帖数: 51 | 18
你说得对。我的解法top down（用一个hashmap记忆），而不是bottom up（DP）。
【在 p**r 的大作中提到】
: 楼主要的是DP解法
:
: String,
|
b*******g
发帖数: 36 | 19
不明白；len2肯定是偶数， java里 len2/2+1和(len2+1)/2+1等于相同的整数，没有
区别啊；
另外把所有所有len2 / 2 + 1改成(len2+1)/2+1， 这里报了错index out of range
error
.....
for (int j = 0; j < len2 / 2; j++){
dp[i + 1][j + 1] = dp[i][j + 1];
.....
【在 p**r 的大作中提到】
: 把代码里所有len2 / 2 + 1改成(len2+1)/2+1就可以了
:
: programming
|
b*******g
发帖数: 36 | 20 谢谢；测了一下，跟上面的dp代码会在下面两个Case输出一样的不正确的值
System.out.println(sln.findMatches("aabangpisebbasepgncccc", "a+b+c-
"));// 0 wrong!
System.out.println(sln.findMatches("aaaaaa", "a+a-"));//0 wrong!
String,
【在 h**********I 的大作中提到】
:
: 你说得对。我的解法top down（用一个hashmap记忆），而不是bottom up（DP）。
|
|
|
b*******g
发帖数: 36 | 21 非corner case 也会出错；比如
System.out.println(sln.findMatches("aabangpisebbasepgncccc", "a+b+c-"));// 0
wrong!
【在 h**********I 的大作中提到】
:
: 你说得对。我的解法top down（用一个hashmap记忆），而不是bottom up（DP）。
|
p**r
发帖数: 5853 | 22 不好意思，昨晚看题的时候，
脑力可能不够傻逼了，把a+b+c+之类的想成abc了，
现在去吃午饭，下午有时间我再仔细看下。
【在 b*******g 的大作中提到】
: 非corner case 也会出错；比如
: System.out.println(sln.findMatches("aabangpisebbasepgncccc", "a+b+c-"));// 0
: wrong!
|
h**********I
发帖数: 51 | 23
c-
我不知道你是怎么测得。我的代买这两个cases都显示1好吗
【在 b*******g 的大作中提到】
: 谢谢；测了一下，跟上面的dp代码会在下面两个Case输出一样的不正确的值
: System.out.println(sln.findMatches("aabangpisebbasepgncccc", "a+b+c-
: "));// 0 wrong!
: System.out.println(sln.findMatches("aaaaaa", "a+a-"));//0 wrong!
:
: String,
|
h**********I
发帖数: 51 | 24
0
我的代码这个case也是显示的1.
你该不会没有save就run了吧。或者你run的还是之前的class里的function。
【在 b*******g 的大作中提到】
: 非corner case 也会出错；比如
: System.out.println(sln.findMatches("aabangpisebbasepgncccc", "a+b+c-"));// 0
: wrong!
|
h**********I
发帖数: 51 | 25 话说我怎么可能连你给的test cases都没有自己测一下就把代码发出来 |
h**********I
发帖数: 51 | 26 这是我的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;
continue;
}
char character = s2.charAt(j * 2);
char op = s2.charAt(j * 2 + 1);
String s2Token = getToken(character, op);
results[i][j] = results[i - 1][j];
if (match(s1, i /*s1's end index*/, s2Token)) {
int s1LastEndIndex = i - s2Token.length();
if (j == 0)
results[i][j] += 1;
else if (s1LastEndIndex >= 0)
results[i][j] += results[s1LastEndIndex][j - 1];
}
}
}
return results[s1Len - 1][s2Len - 1];
} |
r*******g
发帖数: 1335 | 27 还记得找回文数subsequence那道题不？这道题很像啊。
给定aabbcccc, 记录每个地点向右看最近的aa,bb,cccc的位置，这个就是kmp，或者直
接调用strstr。然后就可以dfs了。空间开销也不大，因为输入只是abc，假设输入是3
个字符，那么空间就是N*3。
算法大概是
dfs(){
对当前位置，假设现在已经match了ab，那就在接下来位置找c，每次找的时候利用
前面记录的数组。
}
distinct subsequence不对吧，这里不是删除单个字符。 |
c*****m
发帖数: 271 | 28 感觉是wildcard matching的扩展，a+b+c-转换成*aa*bb*cccc，然后dp的过程中记录次
数，写的python代码如下，测试用例过了：
def match(s, p):
#invalid input
if len(p) % 2 != 0:
return -1
#reconstruct p
temp = ''
i = 0
while i < len(p):
#add '*' first
temp += '*'
#add char pattern
if p[i+1] == '+':
temp += p[i] * 2
else:
#p[i+1] == '-'
temp += p[i] * 4
#iterate to next char
i += 2
p = temp
print p
#wildcard matching
#dp(i,j) the number of ways p[1,i] is matched to s[1,j]
#if p[i-1] == '*': dp(i,j) = dp(i-1,j) + max(dp(i-1,j-1), dp(i,j-1))
# match 0 times 1 times >1 times
#if p[i-1] != '*': dp(i,j) = dp(i-1,j-1) if p[i-1]==s[j-1] else 0
res = 0
#i=0
pre = [0] * (len(s) + 1)
pre[0] = 1 #i=0, j=0
now = [0] * (len(s) + 1)
for i in xrange(1, len(p) + 1):
#i in [1, len(p)]
#j = 0
now[0] = pre[0] if p[i-1] == '*' else 0
for j in xrange(1, len(s) + 1):
#j in [1, len(s)]
if p[i-1] == '*':
now[j] = pre[j] + max(pre[j-1], now[j-1])
#match 0 times 1 times > 1 times
else:
now[j] = pre[j-1] if p[i-1] == s[j-1] else 0
#update result if p is all matched
if i == len(p):
res += now[j]
#iterate to match next i
pre, now = now, pre
#print i, pre
#return reuslt
return res
0
【在 b*******g 的大作中提到】
: 非corner case 也会出错；比如
: System.out.println(sln.findMatches("aabangpisebbasepgncccc", "a+b+c-"));// 0
: wrong!
|
b*******g
发帖数: 36 | 29
谢谢！
【在 h**********I 的大作中提到】
: 这是我的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)
|
b*******g
发帖数: 36 | 30 谢谢你的解答
【在 h**********I 的大作中提到】
: 这是我的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)
|
|
|
b*******g
发帖数: 36 | 31 谢谢
3
【在 r*******g 的大作中提到】
: 还记得找回文数subsequence那道题不？这道题很像啊。
: 给定aabbcccc, 记录每个地点向右看最近的aa,bb,cccc的位置，这个就是kmp，或者直
: 接调用strstr。然后就可以dfs了。空间开销也不大，因为输入只是abc，假设输入是3
: 个字符，那么空间就是N*3。
: 算法大概是
: dfs(){
: 对当前位置，假设现在已经match了ab，那就在接下来位置找c，每次找的时候利用
: 前面记录的数组。
: }
: distinct subsequence不对吧，这里不是删除单个字符。
|
b*******g
发帖数: 36 | 32 谢谢你的解答
【在 c*****m 的大作中提到】
: 感觉是wildcard matching的扩展，a+b+c-转换成*aa*bb*cccc，然后dp的过程中记录次
: 数，写的python代码如下，测试用例过了：
: def match(s, p):
: #invalid input
: if len(p) % 2 != 0:
: return -1
: #reconstruct p
: temp = ''
: i = 0
: while i < len(p):
|
