LeetCode 10. 正規表示式匹配
動態規劃解題要考慮狀態表示和狀態計算
狀態表示分為集合含義和輸出屬性
本題用
f
(
i
,
j
)
f(i,j)
f(i,j)狀態表示，
s
s
s是原字串，
p
p
p是字元規律字串
集合：所有
s
[
1
∼
i
]
s[1 \sim i]
s[1∼i]和
p
[
1
∼
j
]
p[1 \sim j]
p[1∼j]的匹配方案
屬性：bool值，是否存在一個合法方案
狀態計算
1.如果
p
[
j
]
≠
′
∗
′
p[j] \neq '*'
p[j]=′∗′，那麼
f
(
i
,
j
)
=
(
s
[
i
]
=
=
p
[
j
]
∣
∣
p
[
j
]
=
=
′
.
′
)
&
&
f
[
i
−
1
,
j
−
1
]
f(i, j) = (s[i] == p[j] || p[j] == '.') \& \& f[i-1, j-1]
f(i,j)=(s[i]==p[j]∣∣p[j]==′.′)&&f[i−1,j−1]
2.如果
p
[
j
]
=
=
′
∗
′
p[j] == '*'
p[j]==′∗′,那麼需要列舉匹配0個字元，1個字元， 匹配2個字元…
f
(
i
,
j
−
2
)
∣
f
(
i
−
1
,
j
−
2
)
&
s
[
i
]
=
=
p
[
j
]
∣
f
(
i
−
2
,
j
−
2
)
&
s
[
i
]
=
=
p
[
j
]
&
s
[
i
−
1
]
=
=
p
[
j
−
1
]
∣
.
.
.
f(i, j - 2) | f(i - 1, j - 2) \& s[i] == p[j] | f(i-2, j-2) \& s[i] == p[j] \& s[i - 1] == p[j - 1]|...
f(i,j−2)∣f(i−1,j−2)&s[i]==p[j]∣f(i−2,j−2)&s[i]==p[j]&s[i−1]==p[j−1]∣...
狀態數量是
O
(
n
2
)
O(n^2)
O(n2)，轉移全部列舉一遍所以是
O
(
n
)
O(n)
O(n)。整個時間複雜度是
O
(
n
3
)
O(n^3)
O(n3)
這個式子沒辦法被計算機求解，後來發現
所以，總結規律
f
(
i
,
j
)
=
f
(
i
,
j
−
2
)
∣
f
(
i
−
1
,
j
)
&
s
i
=
=
p
j
f(i, j) = f(i, j - 2) | f(i - 1, j) \& s_i == p_j
f(i,j)=f(i,j−2)∣f(i−1,j)&si==pj
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
s = ' ' + s, p = ' ' + p;
vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
f[0][0] = true;
for(int i = 0; i <= n; i ++){
for(int j = 1; j <= m; j ++){
if(j + 1 <= m && p[j + 1] == '*') continue;
if(i && p[j] != '*'){
f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
}else if(p[j] == '*'){
if(j == 1) continue;
f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
}
}
}
return f[n][m];
}
};