c*****u
发帖数: 867 | 1 刚刚面试时遇到了Regular Expression Matching，我是按照下面的答案回答的，
https://simpleandstupid.com/2014/10/14/regular-expression-matching-leetcode-
%E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/
请问它的时间复杂度是多少？我真心晕了，感觉肯定不是mn。 |
x**********1
发帖数: 16 | |
s**********g
发帖数: 14942 | 3 用DP吧
很直观的复杂度
没记错的话就是O(mn)
你给的这个，还要调用O(n)的substring，把整个复杂度分析搞复杂了
leetcode-
【在 c*****u 的大作中提到】
: 刚刚面试时遇到了Regular Expression Matching，我是按照下面的答案回答的，
: https://simpleandstupid.com/2014/10/14/regular-expression-matching-leetcode-
: %E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/
: 请问它的时间复杂度是多少？我真心晕了，感觉肯定不是mn。
|
c*****u
发帖数: 867 | 4 Wildcard那个题可以DP。这个题dp怎么做呢？
【在 s**********g 的大作中提到】
: 用DP吧
: 很直观的复杂度
: 没记错的话就是O(mn)
: 你给的这个，还要调用O(n)的substring，把整个复杂度分析搞复杂了
:
: leetcode-
|
s**********g
发帖数: 14942 | 5 leetcode里discuss里有
我的大概注解是这个：
//Note: analysis here does not have the offset-by-1 adjustment
//match[i][j]: i : p index ; j : s index
//p[i] == '.': match[i][j] = match[i - 1][j - 1]
//p[i] == alphabet: match[i][j] = p[i] == s[j] && match[i - 1][j - 1]
//p[i] == '*': match[i][j] = i > 0 &&
// ( match[i - 2][j] || //0 char
// (pCh[i - 1] == '.' || pCh[i - 1] == sCh[j]) && match[i]
[j - 1] //1 or more chars
// caution on .*: it can match any string
【在 c*****u 的大作中提到】
: Wildcard那个题可以DP。这个题dp怎么做呢？
|
