h******8
发帖数: 55 | 1 The basic idea is fill in a table for a matching path. If the last pair
matches, the whole string will match.
match[i][j] is the array (to match string[i] with pattern[j]), which is of (
string length + 1)*(pattern length + 1).
match[0][*] and match[*][0] is padded with false.
Then the function is something like:
match[i][j] =
1. if pattern char='.', match[i][j]=match[i-1][j-1]
2. if pattern char='*', match[i][j]=match[i][j-1] //match 0 character
||match[i-1][j] //match any character
3. if pattern char=string char, match[i][j]=match[i-1][j-1]
4. otherwise, not matched.
大家看看对不对？ | g**********t
发帖数: 475 | 2 不对。
match[*][0]要初始化为true，因为任何字符串都匹配空模式。这是用来“起头”用的。
match[0][1:n]要初始化为false，因为空字符串不匹配任何非空模式。这用来保证匹配
是完整的。
其他的条件没来的及看。 | h******8
发帖数: 55 | 3 我的意思是好像可以用DP做，为啥大家都用recursion?
的。
【在 g**********t 的大作中提到】
: 不对。
: match[*][0]要初始化为true，因为任何字符串都匹配空模式。这是用来“起头”用的。
: match[0][1:n]要初始化为false，因为空字符串不匹配任何非空模式。这用来保证匹配
: 是完整的。
: 其他的条件没来的及看。
| n*******w
发帖数: 687 | 4 如果像这么定义 .和* 可以用DP。
很多定义是不能DP的，比如
*表示匹配前一个字符任意次
+表示匹配前一个字符至少一次
a-z表示匹配a-z之间任意字符
。。。
有一些不能DP的正则式定义，因为DP的前提是make a choice之后的子问题跟choice本
身没有dependency。
另外正则式搞复杂了，面试不一定有时间用DP写白板。一个面试session 45分钟，一般
3道coding，至少也得2道。时间还是紧张了。当然牛人除外。
(
【在 h******8 的大作中提到】
: The basic idea is fill in a table for a matching path. If the last pair
: matches, the whole string will match.
: match[i][j] is the array (to match string[i] with pattern[j]), which is of (
: string length + 1)*(pattern length + 1).
: match[0][*] and match[*][0] is padded with false.
: Then the function is something like:
: match[i][j] =
: 1. if pattern char='.', match[i][j]=match[i-1][j-1]
: 2. if pattern char='*', match[i][j]=match[i][j-1] //match 0 character
: ||match[i-1][j] //match any character
| j********2
发帖数: 82 | 5 没错。DP只能用来解wildcard,不能解 regex.即使是wildcard,也比递归要难写（反正
我肯定当场白板写不出来）。
【在 n*******w 的大作中提到】
: 如果像这么定义 .和* 可以用DP。
: 很多定义是不能DP的，比如
: *表示匹配前一个字符任意次
: +表示匹配前一个字符至少一次
: a-z表示匹配a-z之间任意字符
: 。。。
: 有一些不能DP的正则式定义，因为DP的前提是make a choice之后的子问题跟choice本
: 身没有dependency。
: 另外正则式搞复杂了，面试不一定有时间用DP写白板。一个面试session 45分钟，一般
: 3道coding，至少也得2道。时间还是紧张了。当然牛人除外。
| h******8
发帖数: 55 | 6 这个不对吧。* in regex can also be done in the following way
if *(pat+1) == ‘*’, regex_match(str, pat) =
• regex_match(str, pat+2) OR // match 0 occurrence – “ab”, “a*
ab”
• regex_match(str+1, pat) if equal_char(*str, *pat) // match 1
occurrence – “aab”, “a*b”
And the above can be achieved with DP:
match[i][j] is the array (to match string[i] with pattern[j]), which is of (
string length + 1)*(pattern length + 1).
Initialize:
match[0][0] = true
match[*][0] = false if str is not empty
match[0][*] = pattern is “a*b*.*”? true:false
Then the function is something like:
match[i][j] =
1. if pattern char='.', match[i][j]=match[i-1][j-1]
2. if pattern char='*', match[i][j]=match[i][j-2] //match 0 character –
to pass “a*”
|| match[i-1][j] if str[i] = pat[j-1] // match 1 occurrence – “aab”, “a*
b”
3. if pattern char=string char, match[i][j]=match[i-1][j-1]
4. otherwise, not matched.
【在 n*******w 的大作中提到】
: 如果像这么定义 .和* 可以用DP。
: 很多定义是不能DP的，比如
: *表示匹配前一个字符任意次
: +表示匹配前一个字符至少一次
: a-z表示匹配a-z之间任意字符
: 。。。
: 有一些不能DP的正则式定义，因为DP的前提是make a choice之后的子问题跟choice本
: 身没有dependency。
: 另外正则式搞复杂了，面试不一定有时间用DP写白板。一个面试session 45分钟，一般
: 3道coding，至少也得2道。时间还是紧张了。当然牛人除外。
|
|
