(Version 1.1)
这一题自己没有做出来，感觉还是思维角度的问题。个人感觉一个可行的思维角度是先从Code Ganker的那个recursive的角度出发(http://blog.csdn.net/linhuanmars/article/details/21145563)，写出一个可行的recursive解法，然后再进一步思考怎么用DP来存储可能会多次用到的中间结果，进而推想到Yu‘s Garden的解法(http://www.cnblogs.com/yuzhangcmu/p/4105529.html)。
（一）最straightforward的brutal force解法，利用recursion思想
首先是recursive的brutal force解法：
1 public class Solution { 2 public boolean isMatch(String s, String p) { 3 return helper(s, p, 0, 0); 4 } 5 6 private boolean helper(String s, String p, int i, int j) { 7 /* first consider if p is used up */ 8 if (j == p.length()) { // 1. p is used up 9 return i == s.length(); 10 } 11 /* then consider if p is not used up */ 12 if (j == p.length() - 1 || p.charAt(j + 1) != ‘*‘) { // 2. compare only the current char 13 // 2 possible situation, p reaches the last or p[j + 1] != ‘*‘ 14 if (i == s.length() || p.charAt(j) != s.charAt(i) && p.charAt(j) != ‘.‘) { 15 return false; 16 } 17 return helper(s, p, i + 1, j + 1); 18 } 19 // 3. need to consider all possible cases since p[j + 1] == ‘*‘ 20 while (i < s.length() && (p.charAt(j) == ‘.‘ || p.charAt(j) == s.charAt(i))) { 21 if (helper(s, p, i, j + 2)) { // starting from ".*" matches nothing 22 return true; 23 } 24 i++; 25 } 26 return helper(s, p, i, j + 2); // all that can be matched to p[j:j+1] has been used 27 } 28 }
首先要去考虑base case是什麽。作为base case的应该是当穷尽了s或者p，因为这时是可以立即得到结果的，如果p（正则表达式）用完了而s有剩余，那么一定不match，这是最简单的情况。
而p没有被用完的情况就是正常的情况了，需要逐个考虑可能性：一是只需考虑p中当前char的，即当前char是p中最后一个（能考虑到把这个情况和后一种情况归类到一起是个挑战）或者当前char后面的一个char不是‘*‘，二是要考虑p的当前char以及紧跟着的‘*‘。第一种情况意味着这时只要两个String中的char不match即可返回false，如果相等，则要由两个String后面的内容决定，于是乎recursively call helper。第二种情况，意味着我们现在考虑到p中的当前char+后面跟着的‘*‘的组合可以在s中match任意多个相同或不同(当组合是".*"时)的char，于是之需要一个while循环，在循环内不停地枚举每一个s中可能与当前p中的组合相match的情况，只要有任何一种情况使得s和p的后面的substring互相match，则可立即返回true，因为毕竟这个helper只是用来判断从某两个下标开始能否match到尽头的。最后当发现所有可能性都不match时，也就是while循环退出时，就需要固定住s中的下标，然后再在p中跳过x+‘*‘这一组合，去调用helper来查看在p中后面的substring有没有可能跟当前下标开始的s中的substring相match。
（二）对recursive brutal force solution的优化，基于DP思想
待续
Regular Expression Matching -- LeetCode
原文：http://www.cnblogs.com/icecreamdeqinw/p/4317183.html