今天天没亮就开始绿了是吧 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Immigration - 落地生根

今天天没亮就开始绿了是吧

今天天没亮就开始绿了是吧# Immigration - 落地生根

b*m2012-09-26 07:09

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];
}

X*a2012-09-26 07:09

2 楼

今天最后一天1：1 AmericanExpress点转BA了？大家都转了吗？不然AE的点还能干点
啥好？

c*t2012-09-26 07:09

3 楼

有个哥们半夜起来，发现绿了，一直绿到有人说下午2点多，呵呵
还有更晚的时间吗？这中间多少绿啦

b*g2012-09-26 07:09

4 楼

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.

l*t2012-09-26 07:09

5 楼

等40% bonus转BA

【在 X***a 的大作中提到】

: 今天最后一天1：1 AmericanExpress点转BA了？大家都转了吗？不然AE的点还能干点
: 啥好？

s*r2012-09-26 07:09

6 楼

哈哈，你说我啊。半夜起来拉肚子。告诉老婆绿了，她也跳起来。

【在 c*******t 的大作中提到】

: 有个哥们半夜起来，发现绿了，一直绿到有人说下午2点多，呵呵
: 还有更晚的时间吗？这中间多少绿啦

s*e2012-09-26 07:09

7 楼

我对这个的理解是
把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;
}
};