1+ package Algorithms .string ;
2+
3+ public class isMatch {
4+ public boolean isMatch (String s ,String p ) {
5+ if (s ==null ||p ==null ) {
6+ return false ;
7+ }
8+
9+ return isMatchRec (s ,p ,0 ,0 );
10+ }
11+
12+ public boolean isMatchRec (String s ,String p ,int indexS ,int indexP ) {
13+ int lenS =s .length ();
14+ int lenP =p .length ();
15+
16+ // we get to the end of the string.
17+ if (indexP ==lenP ) {
18+ return indexS ==lenS ;
19+ }
20+
21+ // only 1 match character left.
22+ if (indexP ==lenP -1 ) {
23+ // String should also have 1 character left.
24+ return indexS ==lenS -1 &&isMatchChar (s .charAt (indexS ),p .charAt (indexP ));
25+ }
26+
27+ // At lease 2 match character left
28+ if (p .charAt (indexP +1 ) =='*' ) {
29+ // match 0;
30+ if (isMatchRec (s ,p ,indexS ,indexP +2 )) {
31+ return true ;
32+ }
33+
34+ // we can match 0 or more.
35+ for (int i =indexS ;i <lenS ;i ++) {
36+ // match once or more.
37+ if (!isMatchChar (s .charAt (i ),p .charAt (indexP ))) {
38+ return false ;
39+ }
40+
41+ if (isMatchRec (s ,p ,i +1 ,indexP +2 )) {
42+ return true ;
43+ }
44+ }
45+
46+ // if any of them does not match, just return false.
47+ return false ;
48+ }
49+
50+ // match current character and the left string.
51+ return indexS <lenS
52+ &&isMatchChar (s .charAt (indexS ),p .charAt (indexP ))
53+ &&isMatchRec (s ,p ,indexS +1 ,indexP +1 );
54+ }
55+
56+ public boolean isMatchChar (char s ,char p ) {
57+ if (p =='*' ) {
58+ return false ;
59+ }
60+
61+ if (s ==p ||p =='.' ) {
62+ return true ;
63+ }
64+
65+ return false ;
66+ }
67+
68+ }