|
| 1 | +//dp |
| 2 | +classSolution { |
| 3 | +funisMatch(s:String,p:String):Boolean { |
| 4 | +val dp=Array (s.length+1) {BooleanArray (p.length+1) } |
| 5 | + dp[0][0]=true |
| 6 | + |
| 7 | +for (iin0..s.length) { |
| 8 | +for (jin1..p.length) { |
| 9 | +if (p[j-1]=='*') { |
| 10 | + dp[i][j]= dp[i][j-2]|| (i>0&& dp[i-1][j]&& (s[i-1]== p[j-2]|| p[j-2]=='.')) |
| 11 | + }else { |
| 12 | + dp[i][j]= i>0&& dp[i-1][j-1]&& (s[i-1]== p[j-1]|| p[j-1]=='.') |
| 13 | + } |
| 14 | + } |
| 15 | + } |
| 16 | + |
| 17 | +return dp[s.length][p.length] |
| 18 | + } |
| 19 | +} |
| 20 | + |
| 21 | +//recursion + memoization |
| 22 | +classSolution { |
| 23 | +funisMatch(s:String,p:String):Boolean { |
| 24 | +val cache=Array (s.length+1) {IntArray (p.length+1) {-1 } } |
| 25 | + |
| 26 | +fundfs(i:Int,j:Int):Int { |
| 27 | +if (i>= s.length&& j>= p.length) |
| 28 | +return1 |
| 29 | +if (j>= p.length) |
| 30 | +return0 |
| 31 | +if (cache[i][j]!=-1) |
| 32 | +return cache[i][j] |
| 33 | + |
| 34 | +val charMatched= i< s.length&& (s[i]== p[j]|| p[j]=='.') |
| 35 | + |
| 36 | +if (j+1< p.length&& p[j+1]=='*') |
| 37 | +returnif (dfs(i, j+2)==1|| charMatched&& dfs(i+1, j)==1)1else0 |
| 38 | +if (charMatched) |
| 39 | +return dfs(i+1, j+1) |
| 40 | + |
| 41 | + cache[i][j]==0 |
| 42 | +return0 |
| 43 | + } |
| 44 | + |
| 45 | +return dfs(0,0)==1 |
| 46 | + } |
| 47 | +} |