g****s 发帖数: 16 | 1 常规问题后,问了个code的问题:
给一个substr,如何判断它在不在给定的str里面。
substr有两个新的符号可能在里面:
(1)* : 0-n个任意字符
(2)? : 1个任意字符
太紧张了,所以面试者简化了题目,说去掉“?”,然后让code和测试:基本框架出来
了,但是好多特殊情况没有处理到,比如substr以“?”起头。
后来又问如果加入“*”有没有思路,刚说了两句就out of time了。
唉,失败了,不知道有没有下文。 |
h****8 发帖数: 599 | |
z*******y 发帖数: 578 | 3 string matching in a phone interview?
It''s difficult to finish this in such a short time, let alone writing code
for that. |
a**********s 发帖数: 588 | 4 I would construct a finite state machine to solve this kind of problem... |
z********y 发帖数: 109 | 5 using "*" and "?" as tokens to split the substr
iterate all indies of the first part, then using recursive if the next token
is "*"
it seems like the DFS scheme
【在 g****s 的大作中提到】 : 常规问题后,问了个code的问题: : 给一个substr,如何判断它在不在给定的str里面。 : substr有两个新的符号可能在里面: : (1)* : 0-n个任意字符 : (2)? : 1个任意字符 : 太紧张了,所以面试者简化了题目,说去掉“?”,然后让code和测试:基本框架出来 : 了,但是好多特殊情况没有处理到,比如substr以“?”起头。 : 后来又问如果加入“*”有没有思路,刚说了两句就out of time了。 : 唉,失败了,不知道有没有下文。
|
g*******y 发帖数: 1930 | 6 好像可以把substr再按照*的位置,划分为若干subsubstr,然后用KMP一个一个找出现的位置,假设subsubstr是abc,d?ef,...,用KMP在string中找到第一个abc出现的位置,然后在c出现之后的string里继续再找d?ef的位置。。。用递归也可以做,速度慢些。
对于?的处理,可以这样处理吧,在比较str和subsubstr的时候,自定义个bool
equalChar(char c1,char c2){ return c1==c2 || c2=='?'}来代替普通的c1 == c2判定。
PS,请问一下lz是怎么拿到ms电面的呢,internal refer,career fair,还是裸投简历? 谢谢。 |
g*******y 发帖数: 1930 | 7 用? 来split不是很好吧。?在kmp预处理的时候,就当作是'?'本身,在比较str和
substr的时候,做为一个通配符。
另外,貌似题目只是问 是否存在match,不是找所有match,不需要DFS。如果找所有match,可以用DP的方法,类似于今年code jam qualification的最后一题。
token
【在 z********y 的大作中提到】 : using "*" and "?" as tokens to split the substr : iterate all indies of the first part, then using recursive if the next token : is "*" : it seems like the DFS scheme
|
z********y 发帖数: 109 | 8 只有在"*"时使用recursive;"?"直接查下一个就行了。
the worst case needs to traverse all nodes in the DFS. Somehow, it is not
necessary for general cases.
match,可以用DP的方法,类似于今年code jam qualification的最后一题。
【在 g*******y 的大作中提到】 : 用? 来split不是很好吧。?在kmp预处理的时候,就当作是'?'本身,在比较str和 : substr的时候,做为一个通配符。 : 另外,貌似题目只是问 是否存在match,不是找所有match,不需要DFS。如果找所有match,可以用DP的方法,类似于今年code jam qualification的最后一题。 : : token
|
M*****a 发帖数: 2054 | 9 简单的词法解析啊
这个自动状态机没多大啊
【在 g****s 的大作中提到】 : 常规问题后,问了个code的问题: : 给一个substr,如何判断它在不在给定的str里面。 : substr有两个新的符号可能在里面: : (1)* : 0-n个任意字符 : (2)? : 1个任意字符 : 太紧张了,所以面试者简化了题目,说去掉“?”,然后让code和测试:基本框架出来 : 了,但是好多特殊情况没有处理到,比如substr以“?”起头。 : 后来又问如果加入“*”有没有思路,刚说了两句就out of time了。 : 唉,失败了,不知道有没有下文。
|
g*******y 发帖数: 1930 | 10 递归方法没错,不过我就是没有理解你说DFS的意思。你说的DFS,应该是针对推广后的
找所有match的问题吧?如果是的话,DFS貌似有重复计算,用dynamic programming比
较好。
【在 z********y 的大作中提到】 : 只有在"*"时使用recursive;"?"直接查下一个就行了。 : the worst case needs to traverse all nodes in the DFS. Somehow, it is not : necessary for general cases. : : match,可以用DP的方法,类似于今年code jam qualification的最后一题。
|
|
|
z********y 发帖数: 109 | 11 每一个token的所有match都是一个node,每一个token到下一个token相当于一条有向的
connected path连接两个node,如果有n个"*",相当于要找一条路径深度为n。找到了,
就结束;一直没有的话,也必须通过DFS遍历所有的node。好像没有重复。
如果找所有的匹配,就是要找所有的深度为n的路径。
【在 g*******y 的大作中提到】 : 递归方法没错,不过我就是没有理解你说DFS的意思。你说的DFS,应该是针对推广后的 : 找所有match的问题吧?如果是的话,DFS貌似有重复计算,用dynamic programming比 : 较好。
|
M*****a 发帖数: 2054 | 12 用一个状态表即可,没多少东西
后的
programming比
【在 z********y 的大作中提到】 : 每一个token的所有match都是一个node,每一个token到下一个token相当于一条有向的 : connected path连接两个node,如果有n个"*",相当于要找一条路径深度为n。找到了, : 就结束;一直没有的话,也必须通过DFS遍历所有的node。好像没有重复。 : 如果找所有的匹配,就是要找所有的深度为n的路径。
|
b***e 发帖数: 1419 | 13 kmp construstion also needs to take ? as wild-card, otherwise your kmp table
is wrong.
match,可以用DP的方法,类似于今年code jam qualification的最后一题。
【在 g*******y 的大作中提到】 : 用? 来split不是很好吧。?在kmp预处理的时候,就当作是'?'本身,在比较str和 : substr的时候,做为一个通配符。 : 另外,貌似题目只是问 是否存在match,不是找所有match,不需要DFS。如果找所有match,可以用DP的方法,类似于今年code jam qualification的最后一题。 : : token
|
g*******y 发帖数: 1930 | 14 I just see that either way is wrong...
table
【在 b***e 的大作中提到】 : kmp construstion also needs to take ? as wild-card, otherwise your kmp table : is wrong. : : match,可以用DP的方法,类似于今年code jam qualification的最后一题。
|
r****o 发帖数: 1950 | 15 谁能给个比较好的针对通配符的子字符串解法?
【在 g*******y 的大作中提到】 : I just see that either way is wrong... : : table
|
b***e 发帖数: 1419 | 16 Why?
【在 g*******y 的大作中提到】 : I just see that either way is wrong... : : table
|
g*******y 发帖数: 1930 | 17 if ? is treated as a normal char when compute KMP table,consider:
str: ababcd....
substr:ab?d
if ? is treated as a Wildcard when compute KMP table, consider:
str: abebcd....
substr:ab?d
【在 b***e 的大作中提到】 : Why?
|
b***e 发帖数: 1419 | 18 The first case is obviously out of question, as indicated in my original
post.
The second case is nothing wrong. The kmp table would be:
a b ? d
0 -1 0 0
which result in no match in
abebcd
【在 g*******y 的大作中提到】 : if ? is treated as a normal char when compute KMP table,consider: : str: ababcd.... : substr:ab?d : if ? is treated as a Wildcard when compute KMP table, consider: : str: abebcd.... : substr:ab?d
|
g****s 发帖数: 16 | 19 校内的career fair。
的位置,假设subsubstr是abc,d?ef,...,用KMP在string中找到第一个abc出现的位置
,然后在c出现之后的string里继续再找d?ef的位置。。。用递归也可以做,速度慢些。
判定。
历? 谢谢。
【在 g*******y 的大作中提到】 : 好像可以把substr再按照*的位置,划分为若干subsubstr,然后用KMP一个一个找出现的位置,假设subsubstr是abc,d?ef,...,用KMP在string中找到第一个abc出现的位置,然后在c出现之后的string里继续再找d?ef的位置。。。用递归也可以做,速度慢些。 : 对于?的处理,可以这样处理吧,在比较str和subsubstr的时候,自定义个bool : equalChar(char c1,char c2){ return c1==c2 || c2=='?'}来代替普通的c1 == c2判定。 : PS,请问一下lz是怎么拿到ms电面的呢,internal refer,career fair,还是裸投简历? 谢谢。
|
p*********a 发帖数: 21 | 20 Maybe KMP is enough! I wrote a program, let me know if there's any bug in it.
#include
#include
#include
#include
using namespace std;
string src, p;
vector v;
vector > next;
void KMP_init(int ix) {
next[ix].resize(v[ix].size());
next[ix][0] = -1;
int i, j;
i = 0; j = -1;
while(i
if(j==-1||v[ix][i]==v[ix][j]||v[ix][i]=='?') {
i++; j++;
if(v[ix][i]==v[ix][j]||v[ix][i]=='?')
next[ix][i] = next[ix][j];
else
next[ix][i] = j |
|
|
g****s 发帖数: 16 | 21 这个代码要在20分钟的电面里面写出来,牛啊!我惭愧~ |
r**u 发帖数: 1567 | 22 这题只要求,给一个substr,如何判断它在不在给定的str里面。substr has ?/*.
不用那么复杂吧,遇到*就skip就可以了,遇到? match下一个。不是?/*就在str里找第
一个substr[next]。
【在 g****s 的大作中提到】 : 常规问题后,问了个code的问题: : 给一个substr,如何判断它在不在给定的str里面。 : substr有两个新的符号可能在里面: : (1)* : 0-n个任意字符 : (2)? : 1个任意字符 : 太紧张了,所以面试者简化了题目,说去掉“?”,然后让code和测试:基本框架出来 : 了,但是好多特殊情况没有处理到,比如substr以“?”起头。 : 后来又问如果加入“*”有没有思路,刚说了两句就out of time了。 : 唉,失败了,不知道有没有下文。
|
h*********e 发帖数: 56 | 23 我在网上看见一个巧妙的解法,不过是指数时间。写 linear time matching 代码对于
面试太难了点。
bool match(const char *pattern, const char *string)
{
switch (*pattern)
{
case '\0': return !*string;
case '*': return match(pattern+1, string) ||
(*string && match(pattern, string+1));
case '?': return *string && match(pattern+1, string+1);
default : return (*pattern == *string) &&
match(pattern+1, string+1);
}
} |
g*****u 发帖数: 298 | 24 如果只找一个match为什么要DFS?
string: abcabcabac
pattern: ab*ab*ac
string在第三个ab的时候mismatch,但是你不需要回溯到前面两个ab的pattern的。就是
说前面两个ab的match不需要再考虑更改了。
【在 z********y 的大作中提到】 : 每一个token的所有match都是一个node,每一个token到下一个token相当于一条有向的 : connected path连接两个node,如果有n个"*",相当于要找一条路径深度为n。找到了, : 就结束;一直没有的话,也必须通过DFS遍历所有的node。好像没有重复。 : 如果找所有的匹配,就是要找所有的深度为n的路径。
|
j***r 发帖数: 69 | 25 我提供一个思路:
先把这个问题简化为---判断substr是否是str的一个suffix. 这个可以用 Dynamic
Programming 在 O(mn)的时间完成。剩下的就容易了。 |
c******f 发帖数: 2144 | |
h*******x 发帖数: 12808 | 27 这个问题挺难啊。
【在 g****s 的大作中提到】 : 常规问题后,问了个code的问题: : 给一个substr,如何判断它在不在给定的str里面。 : substr有两个新的符号可能在里面: : (1)* : 0-n个任意字符 : (2)? : 1个任意字符 : 太紧张了,所以面试者简化了题目,说去掉“?”,然后让code和测试:基本框架出来 : 了,但是好多特殊情况没有处理到,比如substr以“?”起头。 : 后来又问如果加入“*”有没有思路,刚说了两句就out of time了。 : 唉,失败了,不知道有没有下文。
|
w******1 发帖数: 520 | |