题解 | #正则表达式匹配#
正则表达式匹配
http://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4
思路
使用动态规划求解：
1.开辟一个二维数组 dp[i][j]来存放模式串的前j个元素与字符串的前i个元素是否匹配 初始化dp[0][0]为true（表示两个空串是匹配的）
2.如果第pattern[j]==str[i] 或者 pattern[j]=='.' 则 dp[i][j]=dp[i-1][j-1]
3.如果第j个元素是‘’，那么分两种情况有一种情况为true即可。
（1）第一种 a 出现0次，那么dp[i][j-2]==true即表示匹配成功
dp[i][j] = dp[i][j-2]
（2）第二种 a* 出现多次，那么就得是得第str[i]个元素与第pattern[j-1]个元素相等或者第pattern[j-1]个元素是‘.’ 并且dp[i-1][j]=true,则dp[i][j]为true
