p*****2
发帖数: 21240 | 1 刚被问到的，答的比较乱，用的recursion解决的。
两个string，string1是个regular string,
string2 contains one or more '*', each '*' represents 1 or more characters
write a function to find the pattern of string2 in string1, return index. |
y*******g
发帖数: 6599 | 2 只要求返回第一个吗？
把string2 按* break成list of string 然后按顺序 |
p*****2
发帖数: 21240 | 3
只需要返回第一个match的index。×可以代表至少一个character。
如果中间很多个×连着怎么办？
【在 y*******g 的大作中提到】
: 只要求返回第一个吗？
: 把string2 按* break成list of string 然后按顺序
|
y*******g
发帖数: 6599 | 4 连续n个X就至少跳过n在找下一个。
int match(string s1, string s2) {
vector vs;
int p = 0;
int q = 0;
//break s2 to segements
while(true) {
q++;
if(q == s2.size()) {
vs.push_back(s2.substr(p,q-p));
break;
}
if((s2[p] == '*') ^ (s2[q] == '*')) {
vs.push_back(s2.substr(p,q-p));
p = q;
}
}
int index = 0; //to be returned;
int currentIndex = 0;
for(int i=0, n = vs.size(), limit = s1.size(); i
string item = vs[i];
if(item[0] == '*') {
currentIndex += item.length();
if(currentIndex >= limit) {
index = -1;
break; //some * at tail
}
} else {
currentIndex = s1.find(item,currentIndex);
if(currentIndex == -1) {
index = -1; //not found;
break;
}
if(i == 0) {
index = currentIndex;
}
currentIndex += item.length();
}
}
return index;
}
【在 p*****2 的大作中提到】
:
: 只需要返回第一个match的index。×可以代表至少一个character。
: 如果中间很多个×连着怎么办？
|
p*****2
发帖数: 21240 | |
H****s
发帖数: 247 | 6 赞这个解答！
这题只要在string1中找到vs[0]的index, 剩下的就是验证而已, 要么 index valid,
要么不valid.
【在 y*******g 的大作中提到】
: 连续n个X就至少跳过n在找下一个。
: int match(string s1, string s2) {
: vector vs;
: int p = 0;
: int q = 0;
: //break s2 to segements
: while(true) {
: q++;
: if(q == s2.size()) {
: vs.push_back(s2.substr(p,q-p));
|
g**********y
发帖数: 14569 | 7 不能这么干，考虑aabc和a*abc。
这个要用状态机或者recursive来做。
【在 y*******g 的大作中提到】
: 连续n个X就至少跳过n在找下一个。
: int match(string s1, string s2) {
: vector vs;
: int p = 0;
: int q = 0;
: //break s2 to segements
: while(true) {
: q++;
: if(q == s2.size()) {
: vs.push_back(s2.substr(p,q-p));
|
y*******g
发帖数: 6599 | 8 aabc和a*abc本来就不match啊， 因为遇到*就跳过了，从b开始找 abc。
【在 g**********y 的大作中提到】
: 不能这么干，考虑aabc和a*abc。
: 这个要用状态机或者recursive来做。
|
c********1
发帖数: 52 | 9 原题的意思有不用理解吧
each '*' represents 1 or more characters
*可以match a,aa,aaa
但是可以match ab吗
上面那个贴的代码是假设可以match的 |
g**********y
发帖数: 14569 | 10 你在Java里试一试：
System.out.println("aabc".matches("a*abc"));
【在 y*******g 的大作中提到】
: aabc和a*abc本来就不match啊， 因为遇到*就跳过了，从b开始找 abc。
|
y*******g
发帖数: 6599 | 11 java是regex, lz问的不是这个意思
【在 g**********y 的大作中提到】
: 你在Java里试一试：
: System.out.println("aabc".matches("a*abc"));
|
C*********1
发帖数: 6 | 12 我还以为题目是说*表示它前面的character可以出现1次或多次呢, 就是有点类似
regular expression里那样的， 这样的话， aabc和a*abc 应该是match的啊。 |
