[LeetCode]Regular Expression Matching

    String问题的话，总是很容易想到DP。简单的正则匹配也可以用DP来做，不过在用DP之前，由于匹配模式的多种可能，其实我们也可以在解空间遍历所有可能的分支，然后根据需要的情况剪枝，当然backtracking不如DP高效，不过我们可以先试试这个方法。

    基本的情况是三种，我们假设string s是要匹配的字符串，string p是RE，那么当s的第i个之前和p的第j个之前可以匹配的话，我们会出现以下的情况：

• ....../a, ....../c 两个char不匹配
• ....../a, ....../a 或者 ....../a, ....../. 两者匹配
• ....../a, ....../*

    大体上我们会遇到以上三种情况，当然在遇到第三种情况时我们不能遇到了*再进行branch，我们应该在*前面的那个字符开始branch。比如：abd，abc*d，如果我们i到了d并且j到了c的位置，这时候我们发现不同就return false了，所以我们应该提前看下一位是不是*。

• 对于第一种情况，我们简单的返回false即可，因为没有办法匹配了。
• 对于第二种情况，可以匹配，我们接着去看i + 1和 j + 1位。
• 对于第三种情况，就是我们branch的来源，*可以造成多种匹配的模式，首先我们假设j到了某一位并且发现下一位是*, 这时候假设从i开始有一个长度为d的串，j位都可以匹配。比如：....../aaaa，....../a* 或者 ....../abcd，....../.* 这样的模式。长度d可以是>=0的任何数字，当然在string 长度范围内。那么就有(char*)这样一个RE（不是表示指针。。。）可以匹配0, 1, 2..., d个char，总共d + 1个分支。

    那么DFS的终止条件是什么？首先假设我们到了p串的末尾，也就是匹配完了最后一位。发现s串也正好到了末尾，那么当然匹配成功，返回true。相反如果我们发现s串没有到末尾，p串没有其他的char继续匹配了，返回false。另一种情况是，如果我们到了s的末尾，但我们没有到p的末尾（到p末尾的情况跟上面的是一样的 ），那么匹配是还有可能进行的，只要p的后面全部是(char*)这样的RE。那么也就是说，如果我们到了s的末尾，j + 1不是*，我们返回false。相反，如果是*，我们还要让程序继续运行下去，让i去匹配j + 2。

    代码如下：

    接下来是DP的做法，有了上面的分析，我们的思路就更加明确了我们用[i, j]来表示s的前i个char和p的前j个char是否匹配，那么对于以上三种情况：

• 对于第一种情况，赋值false即可。
• 对于第二种情况，[i, j] = [i - 1, j - 1]
• 对于第三种情况，首先如果[i, j - 1]匹配，[i, j]自然也匹配(对应(char*)匹配一个字符的情况)。如果[i , j - 2]匹配，那么[i , j]也匹配(对应(char*)匹配0个字符的情况)。再者，如果[i - 1,  j]匹配，[i,  j]也匹配(对应(char*)匹配s[0, i]末尾多个字符的情况)。

代码如下：

    最后给出Regular Expression的普遍解法，具体的详解可以参考Princeton Algorithms一书的相关章节。简单的概括就是根据p字符串建立NFA，NFA和DFA的区别就是根据输入DFA每次都要相应的转换状态，而NFA没有输入也可以转换状态，也就是说NFA维护的是一个状态的集合，当有输入导致状态转移的时候，所有的维护的状态都要看是否可以转换到下一个状态，转换完之后再看没有输入的话还可以到哪哪些状态，再把这些状态维护起来。继续下一个输入。这里我们用的是Graph来模拟NFA，注意我们有两种edge，但是我们只需要连接epsilon-transition（也就是不需要输入就能进行的状态转移）的edge就行。所有的非epsilon-trainsition都是普通char到char的下一个，这个edge可以在我们每次输入字符的时候把他视为连接。如果有可以进行的转移。我们去到char的下一个字符表示的node。注意我们一共有len + 1个nodes，len是p字符串的长度。额外的node放在末尾表示success，到达sucess才表示我们成功匹配。简而言之，NFA的做法可以分为以下几步：

• 根据p string建立图，连上所有的epsilon-transition代表的edge，不同的符号要连接的epsilon edge不同，具体参考上述书籍。
• dfs第一个字符，找到所有能到的状态。
• 输入s的第一个char，输入char之后找到可以进行的状态转移（对维护的所有状态），去到下一个状态。
• 对所有新找到的状态进行dfs，维护新的所有可以到达的状态。
• 重复第三步直到读完s string
• 在维护的状态中check是否有success，有返回true，否则返回false。

代码如下：