Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita457935

Browse files
committed
feat: add 010
1 parentc284818 commita457935

File tree

2 files changed

+93
-69
lines changed

2 files changed

+93
-69
lines changed

‎note/010/README.md

Lines changed: 59 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -23,71 +23,91 @@ isMatch("ab", ".*") → true
2323
isMatch("aab", "c*a*b") → true
2424
```
2525

26-
**Tags:** String, DynamicProgrammin, Backtracking
26+
**Tags:** String, DynamicProgramming, Backtracking
2727

2828

2929
##思路0
3030

31-
题意是
32-
31+
题意是让让你从判断`s`字符串是否正则匹配于`p`，这道题和[Wildcard Matching][044]很是相似，区别在于`*`，通配符的`*`是可以随意出现的，跟前面字符没有任何关系，其作用是可以表示任意字符串；而正则匹配的`*`不能单独存在，前面必须具有一个字符，其意义是表明前面的这个字符个数可以是任意个数，包括0个。首先我们用递归的方式来实现，其思路如下：
32+
* 如果`s`和`p`都为空，那么返回`true`
33+
* 如果`p`的长度为1，当`s`的长度也为1，并且他们首位匹配则返回`true`，否则返回`false`
34+
* 如果`p`的第二个字符不为'*'，如果`s`为空，那就返回`false`，首位匹配则返回递归调用他们去掉首位的子字符串，否则返回`false`
35+
* 如果`p`的第二个字符为'*'，循环当`s`不为空，且首位匹配，如果递归调用是否匹配`s`字符串和`p`去掉前两位的子字符串，则返回`true`，否则`s`去掉首字母继续循环
36+
* 返回递归调用`s`字符串和`p`去掉前两位的子字符串是否匹配
3337

3438
```java
3539
classSolution {
3640
publicbooleanisMatch(Strings,Stringp) {
37-
if (p.length()==0)return s.length()==0;
41+
if (p.isEmpty())return s.isEmpty();
3842
if (p.length()==1) {
39-
if (s.length()<1)returnfalse;
40-
if (p.charAt(0)!= s.charAt(0)&& p.charAt(0)!='.')returnfalse;
41-
returntrue;
43+
return s.length()==1&& (p.charAt(0)== s.charAt(0)|| p.charAt(0)=='.');
4244
}
4345
if (p.charAt(1)!='*') {
44-
if (s.length()<1)returnfalse;
45-
if (p.charAt(0)!= s.charAt(0)&& p.charAt(0)!='.')returnfalse;
46-
return isMatch(s.substring(1), p.substring(1));
47-
}else {
48-
// match 0 preceding element
46+
if (s.isEmpty())returnfalse;
47+
return (p.charAt(0)== s.charAt(0)|| p.charAt(0)=='.')
48+
&& isMatch(s.substring(1), p.substring(1));
49+
}
50+
// match 1 or more preceding element
51+
while (!s.isEmpty()&& (p.charAt(0)== s.charAt(0)|| p.charAt(0)=='.')) {
4952
if (isMatch(s, p.substring(2)))returntrue;
50-
int i=0;
51-
// match 1 or more preceding element
52-
while (i< s.length()&& (p.charAt(0)== s.charAt(i)|| p.charAt(0)=='.')) {
53-
if (isMatch(s.substring(i+1), p.substring(2))) {
54-
returntrue;
55-
}
56-
++i;
57-
returnfalse;
58-
}
53+
s= s.substring(1);
54+
}
55+
// match 0 preceding element
56+
return isMatch(s, p.substring(2));
57+
}
58+
}
59+
```
60+
61+
62+
##思路1
63+
64+
我们可以把上面的思路更简单化，如下
65+
* 如果`s`和`p`都为空，那么返回`true`
66+
* 如果`p`的第二个字符为`*`，由于`*`前面的字符个数可以为任意，那么我们先递归调用个数为0的情况；或者当`s`不为空，如果他们的首字母匹配，那么我们就递归调用去掉去掉首字母的`s`和完整的`p`
67+
* 如果`p`的第二个字符不为`*`，那么我们就老老实实判断第一个字符是否匹配并且递归调用他们去掉首位的子字符串
68+
69+
```java
70+
classSolution {
71+
publicbooleanisMatch(Strings,Stringp) {
72+
if (p.isEmpty())return s.isEmpty();
73+
if (p.length()>1&& p.charAt(1)=='*') {
74+
return isMatch(s, p.substring(2))
75+
|| (!s.isEmpty()&& (p.charAt(0)== s.charAt(0)|| p.charAt(0)=='.')
76+
&& isMatch(s.substring(1), p));
5977
}
78+
return!s.isEmpty()&& (p.charAt(0)== s.charAt(0)|| p.charAt(0)=='.')
79+
&& isMatch(s.substring(1), p.substring(1));
6080
}
6181
}
6282
```
6383

84+
##思路2
85+
86+
另一种思路就是动态规划了，我们定义`dp[i][j]`的真假来表示`s[0..i)`是否匹配`p[0..j)`，通过思路1，我们可以确定其状态转移方程如下所示：
87+
* 如果`p[j - 1] == '*'`,`dp[i][j] = dp[i][j - 2] || (pc[j - 2] == sc[i - 1] || pc[j - 2] == '.') && dp[i - 1][j];`
88+
* 如果`p[j - 1] != '*'`，`dp[i][j] = dp[i - 1][j - 1] && (pc[j - 1] == '.' || pc[j - 1] == sc[i - 1]);`
89+
90+
6491

6592
```java
6693
classSolution {
6794
publicbooleanisMatch(Strings,Stringp) {
6895
if (p.length()==0)return s.length()==0;
69-
if (p.contains(".*"))returntrue;
7096
int sL= s.length(), pL= p.length();
7197
boolean[][] dp=newboolean[sL+1][pL+1];
98+
char[] sc= s.toCharArray(), pc= p.toCharArray();
7299
dp[0][0]=true;
73-
for (int i=1; i< pL;++i) {
74-
if (p.charAt(i)=='*'&& dp[0][i-1]) {
75-
dp[0][i+1]=true;
100+
for (int i=2; i<= pL;++i) {
101+
if (pc[i-1]=='*'&& dp[0][i-2]) {
102+
dp[0][i]=true;
76103
}
77104
}
78-
for (int i=0; i< sL;++i) {
79-
for (int j=0; j< pL;++j) {
80-
char c1= s.charAt(i), c2= p.charAt(j);
81-
if (c2=='.'|| c2== c1) {
82-
dp[i+1][j+1]= dp[i][j];
83-
}
84-
if (c2=='*') {
85-
c2= p.charAt(j-1);
86-
if (c2== c1|| c2=='.') {
87-
dp[i+1][j+1]= dp[i+1][j]|| dp[i][j+1]|| dp[i+1][j-1];
88-
}else {
89-
dp[i+1][j+1]= dp[i+1][j-1];
90-
}
105+
for (int i=1; i<= sL;++i) {
106+
for (int j=1; j<= pL;++j) {
107+
if (pc[j-1]=='*') {
108+
dp[i][j]= dp[i][j-2]|| (pc[j-2]== sc[i-1]|| pc[j-2]=='.')&& dp[i-1][j];
109+
}else {
110+
dp[i][j]= dp[i-1][j-1]&& (pc[j-1]=='.'|| pc[j-1]== sc[i-1]);
91111
}
92112
}
93113
}
@@ -103,5 +123,6 @@ class Solution {
103123

104124

105125

126+
[044]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/044/README.md
106127
[title]:https://leetcode.com/problems/regular-expression-matching
107128
[ajl]:https://github.com/Blankj/awesome-java-leetcode

‎src/com/blankj/hard/_010/Solution.java

Lines changed: 34 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -10,53 +10,56 @@
1010
*/
1111
publicclassSolution {
1212
// public boolean isMatch(String s, String p) {
13-
// if (p.length() == 0) return s.length() == 0;
13+
// if (p.isEmpty()) return s.isEmpty();
1414
// if (p.length() == 1) {
15-
// if (s.length() < 1) return false;
16-
// if (p.charAt(0) != s.charAt(0) && p.charAt(0) != '.') return false;
17-
// return isMatch(s.substring(1), p.substring(1));
15+
// return s.length() == 1 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');
1816
// }
1917
// if (p.charAt(1) != '*') {
20-
// if (s.length() < 1) return false;
21-
// if (p.charAt(0) != s.charAt(0) && p.charAt(0) != '.') return false;
22-
// return isMatch(s.substring(1), p.substring(1));
23-
// } else {
24-
// // match 0 preceding element
18+
// if (s.isEmpty()) return false;
19+
// return (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')
20+
// && isMatch(s.substring(1), p.substring(1));
21+
// }
22+
// // match 1 or more preceding element
23+
// while (!s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')) {
2524
// if (isMatch(s, p.substring(2))) return true;
26-
// int i = 0;
27-
// // match 1 or more preceding element
28-
// while (i < s.length() && (p.charAt(0) == s.charAt(i) || p.charAt(0) == '.')) {
29-
// if (isMatch(s.substring(i + 1), p.substring(2))) {
30-
// return true;
31-
// }
32-
// ++i;
33-
// }
34-
// return false;
25+
// s = s.substring(1);
26+
// }
27+
// // match 0 preceding element
28+
// return isMatch(s, p.substring(2));
29+
// }
30+
//
31+
// public boolean isMatch(String s, String p) {
32+
// if (p.isEmpty()) return s.isEmpty();
33+
// if (p.length() > 1 && p.charAt(1) == '*') {
34+
// return isMatch(s, p.substring(2))
35+
// || (!s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')
36+
// && isMatch(s.substring(1), p));
3537
// }
38+
// return !s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')
39+
// && isMatch(s.substring(1), p.substring(1));
3640
// }
3741

3842
publicbooleanisMatch(Strings,Stringp) {
3943
if (p.length() ==0)returns.length() ==0;
4044
intsL =s.length(),pL =p.length();
4145
boolean[][]dp =newboolean[sL +1][pL +1];
46+
char[]sc =s.toCharArray(),pc =p.toCharArray();
4247
dp[0][0] =true;
43-
for (inti =1;i <pL; ++i) {
44-
if (p.charAt(i)=='*' &&dp[0][i -1]) {
45-
dp[0][i +1] =true;
48+
for (inti =2;i <=pL; ++i) {
49+
if (pc[i -1]=='*' &&dp[0][i -2]) {
50+
dp[0][i] =true;
4651
}
4752
}
48-
for (inti =0;i <sL; ++i) {
49-
for (intj =0;j <pL; ++j) {
50-
charc1 =s.charAt(i),c2 =p.charAt(j);
51-
if (c2 =='.' ||c2 ==c1) {
52-
dp[i +1][j +1] =dp[i][j];
53+
for (inti =1;i <=sL; ++i) {
54+
for (intj =1;j <=pL; ++j) {
55+
if (pc[j -1] =='.' ||pc[j -1] ==sc[i -1]) {
56+
dp[i][j] =dp[i -1][j -1];
5357
}
54-
if (c2 =='*') {
55-
c2 =p.charAt(j -1);
56-
if (c2 ==c1 ||c2 =='.') {
57-
dp[i +1][j +1] =dp[i +1][j] ||dp[i][j +1] ||dp[i +1][j -1];
58+
if (pc[j -1] =='*') {
59+
if (pc[j -2] ==sc[i -1] ||pc[j -2] =='.') {
60+
dp[i][j] =dp[i -1][j] ||dp[i][j -2];
5861
}else {
59-
dp[i +1][j +1] =dp[i +1][j -1];
62+
dp[i][j] =dp[i][j -2];
6063
}
6164
}
6265
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp