# Wildcard Matching

## Convert to Regular Expression Matching

`?`

->`.`

`*`

->`.*`

This should work, yet, it exceeds the time limited.

## Checkpoint / Timemachine

On modern OS, you can go back to some time you saved if your OS meets some problem. such technology also can be used to solve this problem.

```
S
[ a a b ]
[ a * b * ]
P
P is *, save current state.
```

`P`

goes on to next

```
This state means * matches nothing
S
[ a a b ]
[ a * b * ]
P
```

a mismatch found, `P != S`

, so rollback to checkpoint.

```
This state means * matches a
S
[ a a b ]
[ a * b * ]
P
```

Each `*`

will save to a checkpoint, and retry from nothing until a match is found.

### Remaining tail

Sometimes, `S`

meets the end, but the `P`

not.
In this case, just to check remaining chars in `P`

are all `*`

.

### Source code *Read on Github*

```
1 public class Solution {
2 public boolean isMatch(String s, String p) {
3
4
5 char[] S = s.toCharArray();
6 char[] P = p.toCharArray();
7
8 int checkpointS = -1;
9 int checkpointP = -1;
10
11 int j = 0;
12
13 for(int i = 0; i < S.length; /*void*/){
14
15 if(j < P.length) {
16
17 if(S[i] == P[j] || P[j] == '?'){
18 i++;
19 j++;
20 continue;
21 }
22
23 if(P[j] == '*'){
24
25 checkpointS = i;
26 checkpointP = j;
27
28 j++;
29 continue;
30 }
31 }
32
33 // mismatch
34
35 if(checkpointS >= 0){
36
37 checkpointS++;
38
39 // restore
40 i = checkpointS;
41 j = checkpointP + 1;
42 continue;
43 }
44
45 return false;
46 }
47
48 while(j < P.length) {
49 if(P[j] == '*'){
50 j++;
51 } else {
52 return false;
53 }
54 }
55
56 return true;
57 }
58 }
```