Skip to content

Commit 1bd2fbc

Browse files
fluency03fluency03
committed
RegularExpressionMatching10
1 parent d28cbe4 commit 1bd2fbc

2 files changed

Lines changed: 128 additions & 2 deletions

File tree

‎README.md‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -32,11 +32,11 @@
3232

3333

3434

35-
# Total: 133
35+
# Total: 134
3636

3737
| Easy | Medium | Hard |
3838
|:----:|:------:|:----:|
39-
| 23 | 84 | 26 |
39+
| 23 | 84 | 27 |
4040

4141

4242
| Question | Solution | Difficulty |
@@ -47,6 +47,7 @@
4747
| [4. Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/MedianOfTwoSortedArrays4.java) | Hard |
4848
| [5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/LongestPalindromicSubstring5.java) | Medium |
4949
| [8. String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/StringToInteger8.java) | Medium |
50+
| [10. Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/RegularExpressionMatching10.java) | Hard |
5051
| [14. Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/LongestCommonPrefix14.java) | Easy |
5152
| [15. 3Sum](https://leetcode.com/problems/3sum/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/ThreeSum15.java) | Medium |
5253
| [16. 3Sum Closest](https://leetcode.com/problems/3sum-closest/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/ThreeSumClosest16.java) | Medium |

‎src/RegularExpressionMatching10.java‎

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
/**
2+
* Implement regular expression matching with support for '.' and '*'.
3+
*
4+
* '.' Matches any single character.
5+
* '*' Matches zero or more of the preceding element.
6+
*
7+
* The matching should cover the entire input string (not partial).
8+
*
9+
* The function prototype should be:
10+
* bool isMatch(const char *s, const char *p)
11+
*
12+
* Some examples:
13+
* isMatch("aa","a") → false
14+
* isMatch("aa","aa") → true
15+
* isMatch("aaa","aa") → false
16+
* isMatch("aa", "a*") → true
17+
* isMatch("aa", ".*") → true
18+
* isMatch("ab", ".*") → true
19+
* isMatch("aab", "c*a*b") → true
20+
*
21+
*/
22+
23+
24+
public class RegularExpressionMatching10 {
25+
26+
/**
27+
* https://leetcode.com/problems/regular-expression-matching/solution/
28+
*/
29+
public boolean isMatch(String text, String pattern) {
30+
if (pattern.isEmpty()) return text.isEmpty();
31+
boolean first_match = (!text.isEmpty() &&
32+
(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
33+
34+
if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
35+
return (isMatch(text, pattern.substring(2)) ||
36+
(first_match && isMatch(text.substring(1), pattern)));
37+
} else {
38+
return first_match && isMatch(text.substring(1), pattern.substring(1));
39+
}
40+
}
41+
42+
43+
public boolean isMatch2(String text, String pattern) {
44+
return isMatch(0, 0, text, pattern);
45+
}
46+
47+
public boolean isMatch(int i, int j, String text, String pattern) {
48+
if (j == pattern.length()) return i == text.length();
49+
boolean first_match = (i != text.length() &&
50+
(pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.'));
51+
52+
if (pattern.length() >= j+2 && pattern.charAt(j+1) == '*'){
53+
return (isMatch(i, j+2, text, pattern) ||
54+
(first_match && isMatch(i+1, j, text, pattern)));
55+
} else {
56+
return first_match && isMatch(i+1, j+1, text, pattern);
57+
}
58+
}
59+
60+
61+
public boolean isMatch3(String text, String pattern) {
62+
int textLen = text.length();
63+
int pattLen = pattern.length();
64+
boolean[][] dp = new boolean[textLen+1][pattLen+1];
65+
dp[0][0] = true;
66+
67+
for(int j=1; j<=pattLen; j++) {
68+
if (pattern.charAt(j-1) == '*'){
69+
dp[0][j] = dp[0][j-2];
70+
}
71+
}
72+
73+
for (int i=1; i<=textLen; i++) {
74+
for(int j=1; j<=pattLen; j++) {
75+
if (j >= 2 && pattern.charAt(j-1) == '*') {
76+
boolean preMatch = (pattern.charAt(j-2) == text.charAt(i-1) || pattern.charAt(j-2) == '.');
77+
dp[i][j] = dp[i][j-2] || (preMatch && dp[i-1][j]);
78+
} else {
79+
boolean currMatch = (pattern.charAt(j-1) == text.charAt(i-1) || pattern.charAt(j-1) == '.');
80+
dp[i][j] = currMatch && dp[i-1][j-1];
81+
}
82+
}
83+
}
84+
85+
return dp[text.length()][pattern.length()];
86+
}
87+
88+
89+
/**
90+
* https://leetcode.com/problems/regular-expression-matching/solution/
91+
*/
92+
enum Result {
93+
TRUE, FALSE
94+
}
95+
Result[][] memo;
96+
97+
public boolean isMatch4(String text, String pattern) {
98+
memo = new Result[text.length() + 1][pattern.length() + 1];
99+
return dp(0, 0, text, pattern);
100+
}
101+
102+
public boolean dp(int i, int j, String text, String pattern) {
103+
if (memo[i][j] != null) {
104+
return memo[i][j] == Result.TRUE;
105+
}
106+
boolean ans;
107+
if (j == pattern.length()){
108+
ans = i == text.length();
109+
} else{
110+
boolean first_match = (i < text.length() &&
111+
(pattern.charAt(j) == text.charAt(i) ||
112+
pattern.charAt(j) == '.'));
113+
114+
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
115+
ans = (dp(i, j+2, text, pattern) ||
116+
first_match && dp(i+1, j, text, pattern));
117+
} else {
118+
ans = first_match && dp(i+1, j+1, text, pattern);
119+
}
120+
}
121+
memo[i][j] = ans ? Result.TRUE : Result.FALSE;
122+
return ans;
123+
}
124+
125+
}

0 commit comments

Comments
 (0)