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