k***t
发帖数: 276 | | q****x
发帖数: 7404 | 2 递归。
【在 k***t 的大作中提到】
: 网上有标准解吗？谢。
| k***t
发帖数: 276 | 3 大拿给写个Sample？
【在 q****x 的大作中提到】
: 递归。
| k***t
发帖数: 276 | 4 参照网上的思路，写了一个wildcard match。
做面试用还算简洁。谁给Review一下？
#include
using namespace std;
bool match(char* in, int iidx, char* ptn, int pidx)
{
if (!in || !ptn) return false;
// base case
if (!in[iidx] && !ptn[pidx]) return true;
if (!ptn[pidx]) return false;
if (!in[iidx]) {
while(ptn[pidx]) if (ptn[pidx++]!='*') return false;
return true;
}
if (ptn[pidx]=='?' || ptn[pidx]==in[iidx])
return match(in, iidx+1, ptn, pidx+1);
if (ptn[pidx]=='*') {
while (in[iidx]) {
if (match(in, iidx++, ptn, pidx+1)) return true;
}
while(ptn[++pidx]) if (ptn[pidx]!='*') return false;
return true;
}
return false;
}
int main()
{
char input[] = "regular expression";
char pattern[] = "?egu*pr??*o*";
cout << input << " => " << pattern << " : " <<
match(input, 0, pattern, 0) << endl;
cout << "ab" << " => " << "a" << " : " <<
match("ab", 0, "a", 0) << endl;
}
【在 k***t 的大作中提到】
: 网上有标准解吗？谢。
| i**********e
发帖数: 1145 | 5 请问你的代码是实现 wildcard 还是 regex?
板上之前讨论过。
http://www.mitbbs.com/article_t/JobHunting/31930815.html
【在 k***t 的大作中提到】
: 参照网上的思路，写了一个wildcard match。
: 做面试用还算简洁。谁给Review一下？
: #include
: using namespace std;
: bool match(char* in, int iidx, char* ptn, int pidx)
: {
: if (!in || !ptn) return false;
: // base case
: if (!in[iidx] && !ptn[pidx]) return true;
: if (!ptn[pidx]) return false;
| k***t
发帖数: 276 | 6 我的是.*的wildcard match. 谢谢你的Link.
【在 i**********e 的大作中提到】
: 请问你的代码是实现 wildcard 还是 regex?
: 板上之前讨论过。
: http://www.mitbbs.com/article_t/JobHunting/31930815.html
| i**********e
发帖数: 1145 | 7 我之前制造的一些测试数据（Regular Expression Matching），方便大家用来测试代码：
http://www.leetcode.com/onlinejudge | t****s
发帖数: 1 | 8 a Java version for regex match as below, let me know if there is any issue.
boolean isMatch(String s, String p) throws Exception{
if (p==null || p.length()==0)
return s==null || s.length()==0;
return isMatch(s,p,0,0);
}
boolean isMatch(String s, String p, int is, int ip) throws Exception{
if (ip>=p.length())
return s==null || is>=s.length();
if (ip==p.length()-1 || p.charAt(ip+1)!='*'){
if (p.charAt(ip)=='*')
throw new Exception("illegal");
if (is>=s.length())
return false;
if (p.charAt(ip)!=s.charAt(is) && p.charAt(ip)!='.')
return false;
return isMatch(s,p,is+1,ip+1);
}
is--;
do{
if (isMatch(s,p,++is,ip+2))
return true;
} while (is
(is)));
return false;
} | i**********e
发帖数: 1145 | 9 Your code is correct.
It got "Time Limit Exceeded" due to this test case,
s = "aaaaaaaaaaaaab", p = "a*a*a*a*a*a*a*a*a*a*a*a*c"
which happens to Java solution but not C++ solution.
I have updated the test case so that a Java recursive solution could pass.
Sorry about that.
【在 t****s 的大作中提到】
: a Java version for regex match as below, let me know if there is any issue.
: boolean isMatch(String s, String p) throws Exception{
: if (p==null || p.length()==0)
: return s==null || s.length()==0;
: return isMatch(s,p,0,0);
: }
: boolean isMatch(String s, String p, int is, int ip) throws Exception{
: if (ip>=p.length())
: return s==null || is>=s.length();
: if (ip==p.length()-1 || p.charAt(ip+1)!='*'){
|
|
