由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求教一个string match 的 dp 解法
相关主题
专家们,find the longest common substring of two strings问个题?
aababccbc remove abc这题谁知道答案?
贡献个regular expression DP解法经典面试题
做题做得很郁闷,求指点两个Sorted Array,找K smallest element
50行code能解决addbinary 问题么求一题的完美简洁解答
求教电面遇到的一道pattern match的实现重新看一道经典题
问个Zenefits电面题目,他家好难。。。问个MSFT的题
讨论一道两个linked list的题目求教 合并两数组 并排除重复
相关话题的讨论汇总
话题: string话题: dp话题: int话题: s1话题: s2
1 (共1页)
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
: 可能我解释的不是很清楚,你把我给出的例子走一遍就清楚了。不清楚的地方再问我。

相关主题
求教电面遇到的一道pattern match的实现问个题?
问个Zenefits电面题目,他家好难。。。这题谁知道答案?
讨论一道两个linked list的题目经典面试题
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)。

相关主题
两个Sorted Array,找K smallest element问个MSFT的题
求一题的完美简洁解答求教 合并两数组 并排除重复
重新看一道经典题求两个程序的C++ code
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)

相关主题
问一道题(2)aababccbc remove abc
airBnb电面面经贡献个regular expression DP解法
专家们,find the longest common substring of two strings做题做得很郁闷,求指点
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):

1 (共1页)
相关主题
求教 合并两数组 并排除重复50行code能解决addbinary 问题么
求两个程序的C++ code求教电面遇到的一道pattern match的实现
问一道题(2)问个Zenefits电面题目,他家好难。。。
airBnb电面面经讨论一道两个linked list的题目
专家们,find the longest common substring of two strings问个题?
aababccbc remove abc这题谁知道答案?
贡献个regular expression DP解法经典面试题
做题做得很郁闷,求指点两个Sorted Array,找K smallest element
相关话题的讨论汇总
话题: string话题: dp话题: int话题: s1话题: s2