Implement regular expression matching with support for ‘.‘ and ‘*‘.
‘.‘ Matches any single character.
‘*‘ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
解法1:
这道题中的*表示*之前的那个字符可以有0个，1个或是多个，就是说，字符串a*b，可以表示b或是aaab，即a的个数任意；字符串.*b，可以表示b或是xyzb。需要用递归Recursion来解，大概思路如下：（原字符串为s，正则式为p）
- 若p为空：
- 若p的长度为1：
- 若p的第二个字符不为*：
- 若p的第二个字符为*：
public class Solution { public boolean isMatch(String s, String p) { if (p.isEmpty()) { if (s.isEmpty()) return true; return false; } if (p.length() == 1) return (s.length() == 1 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == ‘.‘)); if (p.charAt(1) != ‘*‘) return (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == ‘.‘) && isMatch(s.substring(1), p.substring(1))); while (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == ‘.‘)) { if (isMatch(s, p.substring(2))) return true; s = s.substring(1); } return isMatch(s, p.substring(2)); } }
上面的方法可以写的更加简洁一些，但是整个思路还是一样的，我们先来判断p是否为空，若为空则根据s的为空的情况返回结果。当p的第二个字符为*号时，由于*号前面的字符的个数可以任意，可以为0，那么我们先用递归来调用为0的情况，就是直接把这两个字符去掉再比较，或者当s不为空，且第一个字符和p的第一个字符相同时，我们再对去掉首字符的s和p调用递归，注意p不能去掉首字符，因为*号前面的字符可以有无限个；如果第二个字符不为*号，那么我们就老老实实的比较第一个字符，然后对后面的字符串调用递归，参见代码如下：
public class Solution { public boolean isMatch(String s, String p) { if (p.isEmpty()) { if (s.isEmpty()) return true; return false; } if (p.length() > 1 && p.charAt(1) == ‘*‘) return (isMatch(s, p.substring(2)) || (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == ‘.‘) && isMatch(s.substring(1), p))); return (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == ‘.‘) && isMatch(s.substring(1), p.substring(1))); } }
解法2:
用动态规划DP来解，用二维数组 dp[i][j] 表示s的前i个字符s[0,i) 和p的前j个字符p[0,j)是否匹配，分以下几种情况：
dp[i][j] = dp[i][j - 2] || (i > 0 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == ‘.‘) && dp[i - 1][j]);
dp[i][j] = i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == ‘.‘) && dp[i - 1][j - 1]
整体代码如下：
public class Solution { public boolean isMatch(String s, String p) { boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]; dp[0][0] = true; for (int i = 0; i <= s.length(); i++) { for (int j = 1; j <= p.length(); j++) { // j从1开始，因为i>0,j=0的情况肯定不匹配 if (j > 1 && p.charAt(j - 1) == ‘*‘) { dp[i][j] = dp[i][j - 2] || (i > 0 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == ‘.‘) && dp[i - 1][j]); // dp[i][j-2]表示*前的字符匹配0次，后面的表示匹配1次以上 } else { // 不为*的时候，需要当前两个字符匹配，同时dp[i-1][j-1] dp[i][j] = i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == ‘.‘) && dp[i - 1][j - 1]; } } } return dp[s.length()][p.length()]; } }
[LeetCode] 10. Regular Expression Matching ☆☆☆☆☆
原文：http://www.cnblogs.com/strugglion/p/6399437.html