4/15/16 Fri
### Wildcard Matching
要点：

- 基本code pattern是以待匹配string s为中心loop，一旦没有任何p的分支match，返回false。如果所有s匹配了，还要检查是不是p也exhausted，一种分支是剩下的p是’*’，这样也可以匹配。
- worst case: s: abcd, p: *e*f*g*h? every *, it swallows all abcd. so it O(n^2)

错误点：

- star和ss：star对应的是’*’这点在pattern中的位置，ss对应的是在上次没有swallow的s点的位置。实际上是记录了可以restore的状态

4/6/16
### Regular Expression Matching及变形
要点
fb的常考题, uber也考过。

思路: recursion是基本的结构: 假设s为待匹配string, p为pattern. 当前要匹配si和pi位置的char. 因为有*的存在, 自然分成两种case: 就是有*和没有*.  如果不是*, 只比较当前2个字符. 如果遇到*, 需要loop si当前位置所有向右(recursion)或者向左(dp)的相同char. 每一个会产生一个新的递归分支. 注意skip当前字符也是一个分支.

recursion:
base condition: 因为递归是向右, 所以如果pi超过pattern, 递归结束.
因为*是和左边的字符关联的, 递归向右的情况, 其条件是p[pi+1]=='*'.
worst case: s: aa…aab, p: a*…a*: 每一层都要loop所有s中的a，loop中的每一个进入一个同样loop的层，形成一个tree structure，所以是O(2^n)，space是O(n)

dp:
base condition: p向右移动
以当前字符是否为*作为条件