b*******m
发帖数: 10 | 1 如下代码，大case 会runtime error 这是什么原因？
哪个大牛帮忙看下
bool isMatch(const char *s, const char *p) {
int lens = strlen(s);
int lenp = strlen(p);
vector> dp(lens+1, vector(false, lenp+1));
dp[lens][lenp] = true;
for (int i = lenp-1; i >= 0; i--) {
if (p[i] == '*' && dp[lens][i+1]) {
dp[lens][i] = true;
} else {
break;
//dp[len][i] = false;
}
}
for (int i = lenp-1; i >= 0; i--) {
for (int j = lens-1; j >= 0; j--) {
if (s[j] == p[i] || p[i] == '?') {
dp[j][i] = dp[j+1][i+1];
} else if (p[i] == '*') {
for (int k = j+1; k <= lens; k++) {
if (dp[k][i+1] == true) {
dp[j][i] = true;
break;
}
}
}
}
}
return dp[0][0];
} | b******g
发帖数: 14 | 2 This problem has a trick. Depending on the size of s and p, you can rule out
the possibility of the match without matching them. | s***e
发帖数: 403 | 3 我对这个的理解是
把pattern按照*分开成子串
然后按照顺序依次搜索
在开头和最后的串要特别调整一下.
class Solution {
public:
#define charMatch(s, p) (p == '?' || p == s)
int subStr (const char* s, int start, const char* p, int len)
{
while (s[start] != 0)
{
if (charMatch (s[start], p[0]))
{
bool match = true;
for (int j = 1; j < len; ++j)
if (s[start + j] == 0)
return -1;
else if (!charMatch (s[start + j], p[j]))
{
match = false;
break;
}
if (match)
return start + len;
}
++start;
}
return -1;
}
#undef charMatch
bool isMatch (const char* s, const char* p)
{
bool front_vary = *p == '*';
bool back_vary = false;
int s_offset = 0;
int p_start = 0;
int p_offset = 0;
while (p[p_offset] != 0)
{
p_start = p_offset;
while (p[p_start] == '*' && p[p_start] != 0) ++p_start;
if (p[p_start] == 0)
{
// is pattern empty?
if (p_start != 0)
back_vary = p[p_start - 1] == '*';
break;
}
p_offset = p_start + 1;
while (p[p_offset] != '*' && p[p_offset] != 0) ++p_offset;
if (p[p_offset] == 0 && p_start != 0)
{
// for the last block we need to do matching backwards
int old_soffset = s_offset;
while (s[s_offset] != 0) ++s_offset;
int pi = p_offset;
int si = s_offset;
while(pi >= p_start && si >= old_soffset)
{
if (p[pi] != '?' && p[pi] != s[si])
return false;
--pi, --si;
}
if (pi >= p_start)
return false; // s does not have enough space
}
else
{
s_offset = subStr (s, s_offset, p + p_start, p_offset -
p_start);
if (s_offset == -1 || (p_start == 0 && !front_vary && s_
offset != p_offset - p_start))
return false;
}
}
if (!back_vary && s[s_offset] != 0)
return false;
else
return true;
}
}; |
|
