H*M
发帖数: 1268 | 1 s1: abcdefg
s2: dcbe
要你找到一个s1中的一个substring,matches s2,但是，这个substring的顺序不重要，
比如bcde also matches dcbe
KMP,和surfix tree都不可以了。
有没有什么efficient的方法？
大家讨论讨论。好象在哪看过这题。 |
a*******h
发帖数: 123 | 2 Simple-minded (m+n)log(m) 够好不？ m = |s1|, n = |s2|。直接在 s1 上搞个BST啥
的。
【在 H*M 的大作中提到】
: s1: abcdefg
: s2: dcbe
: 要你找到一个s1中的一个substring,matches s2,但是，这个substring的顺序不重要，
: 比如bcde also matches dcbe
: KMP,和surfix tree都不可以了。
: 有没有什么efficient的方法？
: 大家讨论讨论。好象在哪看过这题。
|
w********p
发帖数: 948 | 3 substring 得 字母在s1中是连续的吗？
s1: abcdef
s2: bed
结果是 bde 还是 failed.
【在 H*M 的大作中提到】
: s1: abcdefg
: s2: dcbe
: 要你找到一个s1中的一个substring,matches s2,但是，这个substring的顺序不重要，
: 比如bcde also matches dcbe
: KMP,和surfix tree都不可以了。
: 有没有什么efficient的方法？
: 大家讨论讨论。好象在哪看过这题。
|
H*M
发帖数: 1268 | 4 failed.
必须连续
你上次面试怎么样?
【在 w********p 的大作中提到】
: substring 得 字母在s1中是连续的吗？
: s1: abcdef
: s2: bed
: 结果是 bde 还是 failed.
|
b***e
发帖数: 1419 | 5 没必要. 给s2建个按字母表的hash, 扫一遍s1就行了.
【在 a*******h 的大作中提到】
: Simple-minded (m+n)log(m) 够好不？ m = |s1|, n = |s2|。直接在 s1 上搞个BST啥
: 的。
|
H*M
发帖数: 1268 | 6 这个不work吧.是substring,不是sub sequence
【在 b***e 的大作中提到】
: 没必要. 给s2建个按字母表的hash, 扫一遍s1就行了.
|
w********p
发帖数: 948 | 7 我本来也是这样想的。 但如果substring 得 字母在s1中要连续的，要加最后一步
在s1中如果被hash的字母不连续， failed.
1. 看所有s2字母和s1中的字母是否有1对1的关系。有的话，mark s2的字母 （hash)
2. 看被 mark 的s1 字母是否连续
不过如果s1,s2 的string有字母重复好像不可以了
【在 b***e 的大作中提到】
: 没必要. 给s2建个按字母表的hash, 扫一遍s1就行了.
|
w********p
发帖数: 948 | 8 look at your answer.....not good sign
If I have good news, you will know
【在 H*M 的大作中提到】
: failed.
: 必须连续
: 你上次面试怎么样?
|
H*M
发帖数: 1268 | 9 I am really sorry...根本没往那方面想.只是copy你post里的.
I am sensitive to those bad words too...
【在 w********p 的大作中提到】
: look at your answer.....not good sign
: If I have good news, you will know
|
b***e
发帖数: 1419 | 10 有重复也没关系. 两个hash, 一个存s2的inverted index, 一个存现在已经找到的. 设
两个指针i, j来traverse s1(j >= i), 多退(i++)少补(j++), 没找到就重新来过. 唯一
tricky的地方就是如果j++多扫进来一个字母, 假设是a, 那么i++要一直repeat直到把上一个a吐出
来. 沿路经过都要吐出去.
【在 w********p 的大作中提到】
: 我本来也是这样想的。 但如果substring 得 字母在s1中要连续的，要加最后一步
: 在s1中如果被hash的字母不连续， failed.
: 1. 看所有s2字母和s1中的字母是否有1对1的关系。有的话，mark s2的字母 （hash)
: 2. 看被 mark 的s1 字母是否连续
: 不过如果s1,s2 的string有字母重复好像不可以了
|
H*M
发帖数: 1268 | 11 对阿.按你说的
s1: aeeeefg
s2: dcbe
就 return true了.
如果s1中没有s2的组成字母的dup就可以了,看有没有连续的4个
【在 w********p 的大作中提到】
: 我本来也是这样想的。 但如果substring 得 字母在s1中要连续的，要加最后一步
: 在s1中如果被hash的字母不连续， failed.
: 1. 看所有s2字母和s1中的字母是否有1对1的关系。有的话，mark s2的字母 （hash)
: 2. 看被 mark 的s1 字母是否连续
: 不过如果s1,s2 的string有字母重复好像不可以了
|
H*M
发帖数: 1268 | 12 没看懂...
唯一
把上一个a吐出
【在 b***e 的大作中提到】
: 有重复也没关系. 两个hash, 一个存s2的inverted index, 一个存现在已经找到的. 设
: 两个指针i, j来traverse s1(j >= i), 多退(i++)少补(j++), 没找到就重新来过. 唯一
: tricky的地方就是如果j++多扫进来一个字母, 假设是a, 那么i++要一直repeat直到把上一个a吐出
: 来. 沿路经过都要吐出去.
|
b***e
发帖数: 1419 | 13 #include "stdio.h"
#include "string.h"
int c2i(char c) {
return c - 'a';
}
int i2c(int i) {
return i + 'a';
}
int* invertedIndex(char* s) {
int len = strlen(s);
int* hash = new int[26];
for (int i = 0; i < 26; i++) {
hash[i] = 0;
}
for (int i = 0; i < len; i++) {
int c = s[i];
hash[c2i(c)] += 1;
}
return hash;
}
void printHash(int* a) {
for (int i = 0; i < 26; i++) {
printf("%i, ", a[i]);
}
}
int patternMatch(char* s1, c |
w********p
发帖数: 948 | |
