l*****n
发帖数: 246 | 1 String s1 = "
waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";
s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也
就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺
序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有
四个。 | s********l
发帖数: 998 | | l*****a
发帖数: 14598 | 3 不就是brute force吗？
怎么用dp?
【在 s********l 的大作中提到】
: 这个应该用dp把~
| h*********o
发帖数: 230 | 4 LC unique sequence
【在 l*****a 的大作中提到】
: 不就是brute force吗？
: 怎么用dp?
| l*****a
发帖数: 14598 | 5 LC是什么东东？
【在 h*********o 的大作中提到】
: LC unique sequence
| s********l
发帖数: 998 | 6 同学~ 你别来tease我们了~
【在 l*****a 的大作中提到】
: LC是什么东东？
| e*l
发帖数: 11 | 7 感覺有點像leetcode的substring with concatenation of all words 或
Distinct Subsequences
請問有人可以講一下解法嗎？
感謝 | c*******e
发帖数: 373 | 8 这题看着没花招啊
S1 s2各弄个index
挨个比较不就行了
当然s2要先按规则展开 | h*******0
发帖数: 270 | 9 感觉可以time complexity O(n + k) space O(k) k is the s2, n is s1. | c******n
发帖数: 4965 | 10 这后面s2 搞那么多花花不就是给一个string 么？ 然后就是 edit distance , 看s1
通过delete op 怎么变成s2, 跟textbook 讲 do 一模一样还简单点， 就是最后back
trace 麻烦点
【在 l*****n 的大作中提到】
: String s1 = "
: waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
: String s2 = "a+b+c-";
: s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也
: 就是说s2其实是"aabbcccc"，不考虑invalid。
: 在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺
: 序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有
: 四个。
| | | j**********3
发帖数: 3211 | | z*****1
发帖数: 1 | 12 用的dfs 写起来也没有那么复杂
String getCurString(String pat, int patIndex)
{
char curChar = pat.charAt(patIndex);
boolean positive = pat.charAt(patIndex + 1) == '+';
StringBuilder sb = new StringBuilder();
if (positive)
{
sb.append(curChar);
sb.append(curChar);
}
else
{
sb.append(curChar);
sb.append(curChar);
sb.append(curChar);
sb.append(curChar);
}
return sb.toString();
}
public int dfs(String txt, int txtIndex, String pat, int patIndex)
{
int result = 0;
for (int i = 0; i <= patIndex; i+=2)
{
String curString = getCurString(pat, i);
int index = txt.indexOf(curString, txtIndex);
if (index >= 0)
{
if (i == pat.length() - 2)
result += 1;
if (i < pat.length() - 2)
result += dfs(txt, index + 1, pat, i + 2);
}
}
return result;
}
public int possibleMatches(String txt, String pat) {
return dfs(txt, 0, pat, 0);
} | T*****u
发帖数: 7103 | | z*****u
发帖数: 51 | 14 我也被面到了。没写完就brute force搞了。没想到用dp怎么解。 | s********l
发帖数: 998 | | s********l
发帖数: 998 | | k****r
发帖数: 807 | 17 DP, LC distinct subsequence 变形？
int CountDistinctSubseuqence(string text, string p) {
int m = p.size();
int n = text.size();
vector> dp(m+1, vector(n+1, 0));
dp[0][0] = 1;
for (int i = 1; i <= m; i++) dp[i][0] = 0;
for (int j = 1; j <= n; j++) dp[0][j] = 1;
for (int i = 2; i <= m; i += 2) {
for (int j = (p[1] == '+' ? 2 : 4); j <= n; j++) {
char c = p[i-2];
if (p[i-1] == '+') {
if (text[j-2] == c && text[j-1] == c)
dp[i][j] = dp[i-2][j-2] + dp[i][j-1];
else
dp[i][j] = dp[i][j-1];
}
if (p[i-1] == '-') {
if (text[j-4] == c && text[j-3] == c && text[j-2] == c &&
text[j-1] == c)
dp[i][j] = dp[i-2][j-4] + dp[i][j-1];
else
dp[i][j] = dp[i][j-1];
}
}
}
return dp[m][n];
} | H********n
发帖数: 99 | 18 很好的方法。但是有两点不是很明白，
第一就是为什么pattern的index从0开始 return dfs(txt, 0, pat, 0)；
然后dfs method里面循环的终止条件到patIndex？ for (int i = 0; i <= patIndex;
i += 2) {}
【在 z*****1 的大作中提到】
: 用的dfs 写起来也没有那么复杂
: String getCurString(String pat, int patIndex)
: {
: char curChar = pat.charAt(patIndex);
: boolean positive = pat.charAt(patIndex + 1) == '+';
: StringBuilder sb = new StringBuilder();
: if (positive)
: {
: sb.append(curChar);
: sb.append(curChar);
| m******n
发帖数: 51 | 19 Got asked the same question. The question is similar to Leet Code #115
https://leetcode.com/problems/distinct-subsequences/
The DP Solution is in
https://leetcode.com/discuss/26680/easy-to-understand-dp-in-java
But the trick here is you need to group some chars together and treat them
as ONE element. For example, group aa, bb, and cccc together. | m******n
发帖数: 51 | 20 And for S1, bbb needs to break down as "bb" and "bb".
bbbb needs to break down as "bb", "bb", and "bb".
【在 m******n 的大作中提到】
: Got asked the same question. The question is similar to Leet Code #115
: https://leetcode.com/problems/distinct-subsequences/
: The DP Solution is in
: https://leetcode.com/discuss/26680/easy-to-understand-dp-in-java
: But the trick here is you need to group some chars together and treat them
: as ONE element. For example, group aa, bb, and cccc together.
| | | r*****n
发帖数: 35 | 21 val map = new mutable.HashMap[(Int, Int), Int]()
def findNum(s1: String, s2: String, st1: Int, st2: Int): Int = {
map.getOrElseUpdate((st1, st2), {
if (st2 >= s2.length) {
1
} else if (st1 >= s1.length) {
0
} else {
var n = 0
if (s1(st1) == s2(st2)) {
s2(st2+1) match {
case '+' if (st1 +1 < s1.length && s1(st1) == s1(st1 + 1)) =>
n += findNum(s1, s2, st1 +2, st2 + 2)
case '-'
if (st1 + 3 < s1.length && { (1 until 4).foldLeft(true){ case
(m, n) => m && s1(st1 + n) == s1(st1)}}) =>
n += findNum(s1, s2, st1 + 4, st2 + 2)
case _ => n += findNum(s1, s2, st1 + 1, st2 + 1)
}
}
n += findNum(s1, s2, st1 + 1, st2)
n
}
})
} | k**********i
发帖数: 36 | 22 ►►►Regular Expression Matching
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
Method 1: Recursive
Space: O(n) Running Time :O(n^2) 32ms
1) '.' is easy to handle. if p has a '.', it can pass any single character
in s except '\0'.
2) '*' is a totally different problem. if p has a '*' character, it can pass
any length of first-match characters in s including '\0'.
bool matchOne(const char *s, const char *p){
return (*p == *s || (*p == '.' && *s != '\0'));
}
bool isMatch(const char *s, const char *p) {
if (*p == '\0') return *s == '\0'; //empty
if (*(p + 1) != '*') {//without *
if(!matchOne(s,p)) return false;
return isMatch(s + 1, p + 1);
} else { //next: with a *
//try the length of 0
if(isMatch(s, p + 2)) return true;
while ( matchOne(s,p) ) //try all possible lengths
if (isMatch(++s, p + 2)) return true;
}
}
Method 2: DP
Transform method1 into DP with record duplicated subproblem
Space: O(n*m) Running Time :O(n*m) 4ms
bool matchOne(const char s, const char p){
return (p == s || (p == '.' && s != '\0'));
}
bool helper(const char*s, const char *p, int i, int j, int n, int m, int V[n
+1][m+1]){
if(V[i][j] != -1) return V[i][j];
bool ret;
if (p[j+1] != '*') {//without *
if(!matchOne(s[i], p[j])) {
V[i][j] = 0;
return false;
}
ret = helper(s, p, i+1, j+1, n, m, V);
V[i][j] = ret ? 1 : 0;
return ret;
} else { //next: with a *
//try the length of 0
ret = helper(s, p, i, j+2, n, m, V);
if(ret) {
V[i][j] = 1;
return true;
}
int ii = i;
while( matchOne(s[ii],p[j]) ) {//try all possible lengths
ret = helper(s, p, ++ii, j+2, n, m, V );
if(ret) {
V[i][j] = 1;
return true;
}
}
}
V[i][j] = 0;
return false;
}
bool isMatch(const char*s, const char *p){
int n = strlen(s);
int m = strlen(p);
int i,j;
int V[n+1][m+1];
for(i=0;i
for(j=0;j
V[i][j] = -1;
V[n][m] = 1;
// init right
for(i=n-1;i>=0;i--) V[i][m] = 0;
// init bottom
for (j=m-1; j>=0;j--){
if (p[j+1]=='*') V[n][j] = V[n][j+2];
else V[n][j] = 0;
}
return helper(s, p, 0, 0, n, m, V);
}
Method 3: DP fill in dp from bottom right
Space: O(n*m) Running Time :O(n*m) 4ms
bool matchOne(const char *s, const char *p){
return (*p == *s || (*p == '.' && *s != '\0'));
}
bool isMatch(const char *s, const char *p) {
int n = strlen(s);
int m = strlen(p);
int i,j;
bool V[n+1][m+1];
for(i=0;i
for(j=0;j
V[i][j] = false;
V[n][m] = true;
// init bottom
for (i=0; i
// init right
for (j=m-1; j>=0;j--){
if (p[j]=='\0') V[n][j]=true;
if (p[j+1]=='*') V[n][j]=V[n][j+2];
}
// fill in dp from bottom right
for (j=m-1; j>=0; j--){
if (p[j]=='*') continue;
for (i=n-1; i>=0; i--){
if (p[j+1]!='*')
V[i][j] = (s[i]==p[j]||p[j]=='.') ?
V[i+1][j+1] :
false;
else if (V[i][j+2]){ //try the length of 0
V[i][j] = true;
} else {
V[i][j] = (s[i]==p[j]||p[j]=='.') ?
V[i+1][j] :
false;
}
}
}
return V[0][0];
} | w*******u
发帖数: 267 | 23 用你这个方法在unique sequence 那道题里解超时了啊。还是要用到extra space来缩
短运行时间才行啊。还有其他解法吗？
【在 z*****1 的大作中提到】
: 用的dfs 写起来也没有那么复杂
: String getCurString(String pat, int patIndex)
: {
: char curChar = pat.charAt(patIndex);
: boolean positive = pat.charAt(patIndex + 1) == '+';
: StringBuilder sb = new StringBuilder();
: if (positive)
: {
: sb.append(curChar);
: sb.append(curChar);
|
|
