b******7
发帖数: 79 | 1 Desgin an algorithm to find whether a given sting is formed by the
Intealeaving of two given strings. 注意，原来的两个given strings的本身的
character的顺序不能变。
这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
advance both ptrs until they are different and then move one of them back.
The point is who is to be moved back? You cannot simply randomly choose one.
For example,
stringA: ABCEF...
string B: ABCA...
dst string : ABCABCEF....
那么，如果取B's ABCA 就错了。
哪位大侠能指教怎么 |
f*********r
发帖数: 68 | 2 这题要用suffix tree 或者suffix array. 然后求LCP判断一下就可以了
one.
【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
|
j*****j
发帖数: 115 | |
C**********n
发帖数: 100 | 4 能不能把那个例子再说明详细一点呢？
我没怎么看懂。
one.
【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
|
g*******y
发帖数: 1930 | 5 我们算法课作业题
用suffix当然是最好的
不会suffix的话，用DP有两种复杂度
一种是O(A.size * B.size * dist.size)
一种是O(dist.size^2) |
t**e
发帖数: 208 | |
b******7
发帖数: 79 | 7 geniusxsy， 能否指教怎么用suffix tree或者suffix array做啊？ |
g*******y
发帖数: 1930 | 8 呵呵，发现我说错了。这题用suffix tree好像不是很适合呢
就DP做吧
【在 b******7 的大作中提到】
: geniusxsy， 能否指教怎么用suffix tree或者suffix array做啊？
|
g*******y
发帖数: 1930 | 9 你先给interleaving定义一下？
我做的算法课的作业题里面，interleaving的定义是，string的一个subsequence是A的
repeation，剩下的subsequence是B的repeation
repetion的定义是：
ABC的repetion就是ABCABCABC...ABC + '空/A/AB'
one.
【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
|
g*******y
发帖数: 1930 | 10 一般是DP！backtracking的话，是指数复杂度了吧
【在 j*****j 的大作中提到】
: 这种题目一般用backtracking
|
|
|
C**********n
发帖数: 100 | 11 如果"取B' ABCA就错了"
这句话什么意思啊？
谁能说说看?
one.
【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
|
C**********n
发帖数: 100 | 12 能不能说说DP的思路阿？
【在 g*******y 的大作中提到】
: 一般是DP！backtracking的话，是指数复杂度了吧
|
b***e
发帖数: 1419 | 13 Typical DP.
Consider a rectangle network of m*n, where m is the length of a and n
is the length of b. Label the rows using characters in string a and
cols using characters in string b. For your example:
\ a b c e f
a . . . . .
b . . . . .
c . . . . .
a . . . . .
All that you need to do is to find a path from the top left corner to
the bottom right corner. This at most requires you to examine m*n
states, which gives you m*n time complexity. |
C**********n
发帖数: 100 | 14 what does the element [i][j] means?
【在 b***e 的大作中提到】
: Typical DP.
: Consider a rectangle network of m*n, where m is the length of a and n
: is the length of b. Label the rows using characters in string a and
: cols using characters in string b. For your example:
: \ a b c e f
: a . . . . .
: b . . . . .
: c . . . . .
: a . . . . .
: All that you need to do is to find a path from the top left corner to
|
b***e
发帖数: 1419 | 15 Good question, but bad for you not to think.
Assume top left is (0, 0), then element[i][j] is a boolean which means
whether there is a path from (0, 0) to (i, j) that covers the first i+j
characters in the target.
【在 C**********n 的大作中提到】
: what does the element [i][j] means?
|
g*******y
发帖数: 1930 | 16 In fact, element[i][j] is a boolean, indicating whether string[1...i+j] is an interleaving of A[1...i] and B[1...j]
【在 C**********n 的大作中提到】
: what does the element [i][j] means?
|
g*******y
发帖数: 1930 | 17 in case of A string B string are repetion of small size string A' and B'
there's an DP algorithm that takes O(string.size * A'.size * B'.size)
so in cases where sizes of A' B' are very small, this algorithm will be much
better.
【在 b***e 的大作中提到】
: Typical DP.
: Consider a rectangle network of m*n, where m is the length of a and n
: is the length of b. Label the rows using characters in string a and
: cols using characters in string b. For your example:
: \ a b c e f
: a . . . . .
: b . . . . .
: c . . . . .
: a . . . . .
: All that you need to do is to find a path from the top left corner to
|
b***e
发帖数: 1419 | 18 // I don't see why I didn't explain enough, or, you didn't understand
enough?
"A path from (0, 0) to (i, j)" is not a bit different from "an
interleaving of A[1...i] and B[1...j]".
is an interleaving of A[1...i] and B[1...j]
【在 g*******y 的大作中提到】
: In fact, element[i][j] is a boolean, indicating whether string[1...i+j] is an interleaving of A[1...i] and B[1...j]
|
C**********n
发帖数: 100 | 19 那也就是说，
不用看什么从[0][0]到[M][N]有什么路径，而是直接看[M][N]=1就可以了把？
an interleaving of A[1...i] and B[1...j]
【在 g*******y 的大作中提到】
: In fact, element[i][j] is a boolean, indicating whether string[1...i+j] is an interleaving of A[1...i] and B[1...j]
|
g*******y
发帖数: 1930 | 20 呵呵，不好意思，我回帖子的时候你还没发解释，等我吃了顿饭回来把回帖发了才发现
你已经解释了。。。
【在 b***e 的大作中提到】
: // I don't see why I didn't explain enough, or, you didn't understand
: enough?
: "A path from (0, 0) to (i, j)" is not a bit different from "an
: interleaving of A[1...i] and B[1...j]".
:
: is an interleaving of A[1...i] and B[1...j]
|
|
|
g*******y
发帖数: 1930 | 21 看[1][str.size-1] || [2][str.size-2] ||...|| [str.size-1][1]
看辅对角线
【在 C**********n 的大作中提到】
: 那也就是说，
: 不用看什么从[0][0]到[M][N]有什么路径，而是直接看[M][N]=1就可以了把？
:
: an interleaving of A[1...i] and B[1...j]
|
k*k
发帖数: 49 | 22 /* a simple brute force sol.
similar to the sol. of another m$ problem:
matching a*?b with adxefb
*/
int isInterleaving(char* a, char* b, char* c,
int ai, int bi, int ci){
printf("entry info: %d, %d, %d,\n", ai, bi, ci);
if (a[0]=='\0' && b[0]=='\0' && c[0]=='\0')
return 1;
if (b[0]=='\0' && a[0]=='\0' && c[0]!='\0')
return 0;
int tmp1=0; int tmp2=0;
if (a[0]!='\0' && a[0]==c[0]){
tmp1 = isInterleaving(a+1, b, c+1,
ai+1, bi, ci+1);
}
if (tmp |
g*******y
发帖数: 1930 | 23 I think you are likely to fail the interview if you do something like this...
【在 k*k 的大作中提到】
: /* a simple brute force sol.
: similar to the sol. of another m$ problem:
: matching a*?b with adxefb
: */
: int isInterleaving(char* a, char* b, char* c,
: int ai, int bi, int ci){
: printf("entry info: %d, %d, %d,\n", ai, bi, ci);
: if (a[0]=='\0' && b[0]=='\0' && c[0]=='\0')
: return 1;
: if (b[0]=='\0' && a[0]=='\0' && c[0]!='\0')
|
k*k
发帖数: 49 | 24 如果可能，您是否可以贴个 DP 的implementation.
先谢了。 |
k*k
发帖数: 49 | 25 @geniusxsy; thanks,
//my dp solution.
int isInterleavingdp(char* a, char* b, char* str, int alen, int blen){
int i, j;
int m[alen+1][blen+1];
memset(m, 0, (alen+1)*(blen+1)*sizeof(int));
for(i=0; i
if (a[i]==str[i])
m[i+1][0]=1;
else
break;
}
for(j=0; j
if (b[j] == str[j])
m[0][j+1]=1;
else
break;
}
for(i=1; i<=alen; i++){
for(j=1; j<=blen; j++){
int r1 = (m[i-1][j]>0) && a[i-1]==str[i+j-1];
int r2 |
g*******y
发帖数: 1930 | 26 use bool m[][] to save space.
or even better,
you compute the matrix line by line in 次对角线 direction, this way you'll
need only O(N) space.
【在 k*k 的大作中提到】
: @geniusxsy; thanks,
: //my dp solution.
: int isInterleavingdp(char* a, char* b, char* str, int alen, int blen){
: int i, j;
: int m[alen+1][blen+1];
: memset(m, 0, (alen+1)*(blen+1)*sizeof(int));
:
: for(i=0; i: if (a[i]==str[i])
: m[i+1][0]=1;
|
b******7
发帖数: 79 | 27 感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！ |
b******7
发帖数: 79 | 28 感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！ |
b******7
发帖数: 79 | 29 感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！ |
b******7
发帖数: 79 | 30 感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！ |
|
|
k*k
发帖数: 49 | 31 hi, geniusxsy
i am not quite get the "次对角线 direction" idea.
if possible, could you kindly elaborate... such as give me an simple example.
char* a="ab";
char* b="de";
char* c="adbe";
thank u so much. |
b******7
发帖数: 79 | 32 感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！ |
b******7
发帖数: 79 | 33 感谢大家啊，我昨天也响了想，blaze的答案是对的。复杂度就是O(mn)，而且最后一个
点B（m,n）=1就可以说明是true了。多谢大家！ |
b******7
发帖数: 79 | 34 感谢大家，我也想了想，blaze的答案确实对，另外B(m,n)==1 应该就能说明true |
b******7
发帖数: 79 | 35 感谢大家，我也想了想，blaze的答案确实对，另外B(m,n)==1 应该就能说明true |
b***e
发帖数: 1419 | 36 Are you a robot? LOL
【在 b******7 的大作中提到】
: 感谢大家，我也想了想，blaze的答案确实对，另外B(m,n)==1 应该就能说明true
|
b***e
发帖数: 1419 | 37 Roughly:
for (int s = 0; s < m+n; s++) {
for (int i = 0; i < s; i++) {
int j = s - i;
element[i][j] =
(element[i-1][j] && a[i] = t[s]) ||
(element[i][j-1] && b[j] = t[s]);
}
}
where s identifies a diagonal.
【在 k*k 的大作中提到】
: @geniusxsy; thanks,
: //my dp solution.
: int isInterleavingdp(char* a, char* b, char* str, int alen, int blen){
: int i, j;
: int m[alen+1][blen+1];
: memset(m, 0, (alen+1)*(blen+1)*sizeof(int));
:
: for(i=0; i: if (a[i]==str[i])
: m[i+1][0]=1;
|
s*x
发帖数: 3328 | 38 做一个NFA接受(A+B)^*，然后看这个NFA是不是接受你给的那个字符串。就是复杂度不
小。
one.
【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
|
P*****f
发帖数: 2272 | 39 baseline的解法就是dp了.O(MN)
当然在实际中可以根据输入先算一些hash值,提高amortized performance
one.
【在 b******7 的大作中提到】
: Desgin an algorithm to find whether a given sting is formed by the
: Intealeaving of two given strings. 注意，原来的两个given strings的本身的
: character的顺序不能变。
: 这个题不简单，因为你不能简单的用3个指针分别指向三个string,遇到string A的就拷
: 贝到dst string,遇到string B的就拷贝他的。最麻烦的在于遇到A,B都相同的，你不能
: advance both ptrs until they are different and then move one of them back.
: The point is who is to be moved back? You cannot simply randomly choose one.
: For example,
: stringA: ABCEF...
: string B: ABCA...
|
