C***U
发帖数: 2406 | 1 Simple regular expression match，only 3 possible patterns：
a-z : match a-z
a+ : match any numbers of a
.+ : repeat 1 - arbitrary times
和没用过regex的同学解释一下 例如
a+b 可以match : ab, aab, aaaaaaaaaaab
b.+b 可以match : bb, bab, b12345b
有什么好的办法没？ |
k****r
发帖数: 807 | |
w****x
发帖数: 2483 | 3 /*
Write the actual code to parse a regular expression including "*",
which stands for 0 or more previous characters, "+", which
stands for 1 or more previous characters, and ".",
which stands for 1 exact character
*/
bool isMatch(const char *s, const char *p) {
assert(s && p);
if (*p == 0)
return *s == 0;
if (*(p+1) != '*')
return ((*p == '.' && *s != 0) || *s == *p) && isMatch(s+1, p+1);
const char* q = s;
while ((*p == '.' || *p == *q) && *q != 0)
{
if (isMatch(q, p+2))
return true;
q++;
}
return isMatch(q, p+2);
} |
l****o
发帖数: 315 | 4 这递归动归都可以啊. 如果我没记错... 就是leetcode那道吧...而且条件还化简了一
点. |
C***U
发帖数: 2406 | 5 递归时间太慢了
【在 l****o 的大作中提到】
: 这递归动归都可以啊. 如果我没记错... 就是leetcode那道吧...而且条件还化简了一
: 点.
|
h********6
发帖数: 285 | 6 这题递归可以接受，能够过leetcode
【在 C***U 的大作中提到】
: 递归时间太慢了
|
p*****2
发帖数: 21240 | |
c********t
发帖数: 5706 | 8 Dear Googler,
你的题，从此不做解答
留一条非死不可的路让俺们走吧。
这题用leetcode re的解法不能解吗？看着更容易啊。
【在 C***U 的大作中提到】
: Simple regular expression match，only 3 possible patterns：
:
: a-z : match a-z
: a+ : match any numbers of a
: .+ : repeat 1 - arbitrary times
:
: 和没用过regex的同学解释一下 例如
: a+b 可以match : ab, aab, aaaaaaaaaaab
: b.+b 可以match : bb, bab, b12345b
: 有什么好的办法没？
|
N*********6
发帖数: 4372 | 9 b.+b match不了bb吧，.+必须要有一个字符出现至少一次
【在 C***U 的大作中提到】
: Simple regular expression match，only 3 possible patterns：
:
: a-z : match a-z
: a+ : match any numbers of a
: .+ : repeat 1 - arbitrary times
:
: 和没用过regex的同学解释一下 例如
: a+b 可以match : ab, aab, aaaaaaaaaaab
: b.+b 可以match : bb, bab, b12345b
: 有什么好的办法没？
|
p*****2
发帖数: 21240 | 10
昨天晚上想问这个来着
【在 N*********6 的大作中提到】
: b.+b match不了bb吧，.+必须要有一个字符出现至少一次
|
|
|
C***U
发帖数: 2406 | 11 有人说可以用finite state machine的做法
不知道有人试过么？
【在 c********t 的大作中提到】
: Dear Googler,
: 你的题，从此不做解答
: 留一条非死不可的路让俺们走吧。
: 这题用leetcode re的解法不能解吗？看着更容易啊。
|
C***U
发帖数: 2406 | 12 应该是可以0次吧
这个题目不是我的
直接拷贝的
【在 N*********6 的大作中提到】
: b.+b match不了bb吧，.+必须要有一个字符出现至少一次
|
l*****a
发帖数: 14598 | 13 这种题我最早都这么做
后来才发现有leetcode的做法
【在 C***U 的大作中提到】
: 有人说可以用finite state machine的做法
: 不知道有人试过么？
|
l****o
发帖数: 315 | 14 Finite state machine? AC算法？
【在 C***U 的大作中提到】
: 有人说可以用finite state machine的做法
: 不知道有人试过么？
|
C***U
发帖数: 2406 | 15 大牛给个你说的leetcode的解法的链接
【在 l*****a 的大作中提到】
: 这种题我最早都这么做
: 后来才发现有leetcode的做法
|
C***U
发帖数: 2406 | 16 贴个出来看看
呵呵
或者给个链接
【在 l****o 的大作中提到】
: Finite state machine? AC算法？
|
c********t
发帖数: 5706 | |
t****a
发帖数: 1212 | 18 这个是map .*的dp算法，用memoize recursion实现，包括测试数据。改成.+很简单。
懒得改了。
(defn ch-match [c1 c2]
(if (= c2 \.)
true
(if (= c1 c2)
true
false)))
(def str-match
(memoize
(fn [str1 str2]
(cond (and (empty? str1) (empty? str2)) true
(or (empty? str1) (empty? str2)) false
:else (let [c1 (peek str1)
c2 (peek str2)]
(if (= c2 \*)
(let [c3 (peek (pop str2))]
(if (ch-match c1 c3)
(or (str-match (pop str1) str2) (str-match str1 (
pop (pop str2))) (str-match (pop str1) (pop (pop str2))))
(str-match str1 (pop (pop str2)))))
(if (ch-match c1 c2)
(str-match (pop str1) (pop str2))
false)))))))
(defn regex [str1 str2]
(let [s1 (vec (str "a" str1))
s2 (vec (str "a" str2))]
(str-match s1 s2)))
(regex "abbcacbbbbbabcbaca" "a*a*.*a*.*a*.b*a*") ; true
(regex "babcacbbbacaacca" "a*.b.*a.*.*a*b*c") ; false
(regex "baccbbcbcacacbbc" "c*.*b*c*ba*b*b*.a*") ; true
(regex "bbaaaacabccbcac" "b*b*a*c*c*a*c*.*") ; true
(regex "bacacbacaaabccbcbaa" "a*.c*c*c*a*b*..*") ; true
(regex "ababccbabababbbbc" ".*a*ba*.a*b*a*.*b.*") ; true
(regex "aaaaabaccbbccababa" "a*b*.*c*c*.*.*.*c") ; false
(regex "ababbcaaabbaccb" "c*c*..*a*a*a*.*") ; true |
C***U
发帖数: 2406 | |
c********t
发帖数: 5706 | 20 这题应该有不用递归的DP解法吧？
可惜我做不出。求高人。
【在 C***U 的大作中提到】
: 这个是递归的么
|
d**********x
发帖数: 4083 | 21 regex本质上就是NFA或者DFA。。。
【在 C***U 的大作中提到】
: 有人说可以用finite state machine的做法
: 不知道有人试过么？
|
A*****i
发帖数: 3587 | |
