1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Oct 26, 2014
4+ Problem: Regular Expression Matching
5+ Difficulty: Hard
6+ Source: https://oj.leetcode.com/problems/regular-expression-matching/
7+ Notes:
8+ Implement regular expression matching with support for '.' and '*'.
9+ '.' Matches any single character.
10+ '*' Matches zero or more of the preceding element.
11+ The matching should cover the entire input string (not partial).
12+ The function prototype should be:
13+ bool isMatch(const char *s, const char *p)
14+ Some examples:
15+ isMatch("aa","a") ? false
16+ isMatch("aa","aa") ? true
17+ isMatch("aaa","aa") ? false
18+ isMatch("aa", "a*") ? true
19+ isMatch("aa", ".*") ? true
20+ isMatch("ab", ".*") ? true
21+ isMatch("aab", "c*a*b") ? true
22+
23+ Solution: 1. Recursion.
24+ 2. DP.
25+ */
26+
27+ public class Solution {
28+ public boolean isMatch_1 (String s ,String p ) {
29+ if (p .length () ==0 )return s .length () ==0 ;
30+ if (p .length () ==1 ) {
31+ if (s .length () !=1 )return false ;
32+ return (s .charAt (0 ) ==p .charAt (0 )) || (p .charAt (0 ) =='.' );
33+ }
34+ if (s .length () !=0 && (p .charAt (0 ) ==s .charAt (0 ) || (p .charAt (0 ) =='.' ))) {
35+ if (p .charAt (1 ) =='*' )
36+ return isMatch (s .substring (1 ),p ) ||isMatch (s ,p .substring (2 ));
37+ return isMatch (s .substring (1 ),p .substring (1 ));
38+ }
39+ return p .charAt (1 ) =='*' &&isMatch (s ,p .substring (2 ));
40+ }
41+ public boolean isMatch_2 (String s ,String p ) {
42+ if (p .length () ==0 )return s .length () ==0 ;
43+ int sLen =s .length (),pLen =p .length ();
44+ boolean [][]dp =new boolean [sLen +1 ][pLen +1 ];
45+ dp [0 ][0 ] =true ;
46+ for (int i =2 ;i <=pLen ; ++i ) {
47+ dp [0 ][i ] =dp [0 ][i -2 ] &&p .charAt (i -1 ) =='*' ;
48+ }
49+ for (int i =1 ;i <=sLen ; ++i ) {
50+ for (int j =1 ;j <=pLen ; ++j ) {
51+ char ch1 =s .charAt (i -1 ),ch2 =p .charAt (j -1 );
52+ if (ch2 !='*' )dp [i ][j ] =dp [i -1 ][j -1 ] && (ch1 ==ch2 ||ch2 =='.' );
53+ else {
54+ dp [i ][j ] =dp [i ][j -2 ];
55+ if (ch1 ==p .charAt (j -2 ) ||p .charAt (j -2 ) =='.' )
56+ dp [i ][j ] =dp [i ][j ] |dp [i -1 ][j ];
57+ }
58+ }
59+ }
60+ return dp [sLen ][pLen ];
61+ }
62+ }
