8000 add 44 · deepakavs/Leetcode@030778e · GitHub
[go: up one dir, main page]
Skip to conte 8000 nt

Commit 030778e

Browse files
fishercoder1534fishercoder1534
committed
add 44
1 parent 03742a2 commit 030778e

File tree

2 files changed

+52
-0
lines changed

2 files changed

+52
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -477,6 +477,7 @@ Your ideas/fixes/algorithms are more than welcome!
477477
|47|[Permutations II](https://leetcode.com/problems/permutations-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_47.java)|O(n*n!)|O(n)|Medium|Backtracking
478478
|46|[Permutations](https://leetcode.com/problems/permutations/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_46.java)|O(n*n!)|O(n)|Medium|Backtracking
479479
|45|[Jump Game II](https://leetcode.com/problems/jump-game-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/JumpGameII.java)|O(?)|O(?)|Hard|
480+
|44|[Wildcard Matching](https://leetcode.com/problems/wildcard-matching/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_44.java)|O(m*n)|O(m*n)|Hard| Backtracking, DP, Greedy, String
480481
|43|[Multiply Strings](https://leetcode.com/problems/multiply-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_43.java)|O(n)|O(1)|Medium| Array, String
481482
|42|[Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)|[Solution](../master/src/main/java/com/fishercoder/solutions/TrappingRainWater.java)|O(n)|O(1)|Hard|
482483
|41|[First Missing Positive](https://leetcode.com/problems/first-missing-positive/)|[Solution](../master/src/main/java/com/fishercoder/solutions/FirstMissingPositive.java)|O(n)|O(1)|Hard|

‎src/main/java/com/fishercoder/solutions/_44.java

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package com.fishercoder.solutions;
2+
3+
/**
4+
* 44. Wildcard Matching
5+
* Implement wildcard pattern matching with support for '?' and '*'.
6+
7+
'?' Matches any single character.
8+
'*' Matches any sequence of characters (including the empty sequence).
9+
10+
The matching should cover the entire input string (not partial).
11+
12+
The function prototype should be:
13+
bool isMatch(const char *s, const char *p)
14+
15+
Some examples:
16+
isMatch("aa","a") → false
17+
isMatch("aa","aa") → true
18+
isMatch("aaa","aa") → false
19+
isMatch("aa", "* EEA6 ") → true
20+
isMatch("aa", "a*") → true
21+
isMatch("ab", "?*") → true
22+
isMatch("aab", "c*a*b") → false
23+
*/
24+
public class _44 {
25+
26+
public boolean isMatch(String s, String p) {
27+
boolean[][] match = new boolean[s.length()+1][p.length()+1];
28+
match[s.length()][p.length()] = true;
29+
for (int i = p.length()-1; i >= 0; i--) {
30+
if (p.charAt(i) != '*') {
31+
break;
32+
} else {
33+
match[s.length()][i] = true;
34+
}
35+
}
36+
37+
for (int i = s.length()-1; i >= 0; i--) {
38+
for (int j = p.length()-1; j >= 0; j--) {
39+
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
40+
match[i][j] = match[i+1][j+1];
41+
} else if (p.charAt(j) == '*') {
42+
match[i][j] = match[i+1][j] || match[i][j+1];
43+
} else {
44+
match[i][j] = false;
45+
}
46+
}
47+
}
48+
return match[0][0];
49+
}
50+
51+
}

0 commit comments

Comments
 (0)
0