10. 正则表达式匹配

Introduction

Question：10. 正则表达式匹配

Analysis

不妨令dp[i][j]表示s[0:i]与p[0:j]是否匹配的上，那么：

• s[i] == p[j] || p[j] == '.' => dp[i][j] = dp[i-1][j-1]
• p[j] == '*' && s[i] != p[j-1] => dp[i][j] = dp[i][j-2]（a* => ''）
• p[j] == '*' && s[i] == p[j-1] => dp[i][j] = dp[i][j-2] || dp[i-1][j] || dp[i-1][j-1]（a* => '' || a* => a*a || a* => ''）
• i == 0 && j == 0 => true
• i == 0 || j == 0 => false

Implement

One More Thing