Regular Expression Matching

Question

 Solution 

 

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

Hide Tags

 

SOLUTION1:

总的来说思路是递归。

判断下一个字符是否是*：

如果不是*，则判断当前字符是否匹配。

如果是*，则因为不能确定*到底会匹配几个，在当前字符匹配的前提下，要枚举所有的情况，从假设匹配0个，1个，2个。。。只要有一种情况成功了，最终也就成功了。

我们可以从0开始，先考虑直接跳过当前2个正则字符，然后再1个，2个继续搜索下去。

如果是*，但是当前字符不匹配，则跳过两个递归。

具体的代码如下，注释写得很清楚。

ref: 

1 package Algorithms; 2  3 public class IsMach { 4     public static void main(String[] str) { 5         //System.out.println(isMatch("aa", "aa")); 6         System.out.println(isMatch("aab", "c*a*b")); 7     } 8      9     public static boolean isMatch(String s, String p) {10         if (s == null || p == null) {11             return false;12         }13         14         return help(s, p, 0, 0);15     }16     17     public static boolean help(String s, String p, int indexS, int indexP) {18         int pLen = p.length();19         int sLen = s.length();20         21         // 1. P结束了，这时 S也应该要结束 22         if (indexP == pLen) {23             return indexS == sLen;  24         }25         26         // 2. P 只有最后一个没有匹配27         if (indexP == pLen - 1) {28             // 必须相等，或者是p为'.'.  29             // S必须只有一个字符30             return indexS == sLen - 1 && matchChar(s, p, indexS, indexP);31         }32         33         // 以下P 至少还有2个字符.34         35         // 2. 单独匹配的情况, 如 aa, a. 类似这样36         if (p.charAt(indexP + 1) != '*') {37            if (indexS < sLen && matchChar(s, p, indexS, indexP)) {38                return help(s, p, indexS + 1, indexP + 1);  // p可以前进一格39            } else {40                return false;41            }42         }43         44         // 3. 多重匹配的情况, 如 .* or a* ,这时需要进行递归45         46         // 先直接跳过此2个正则，因为我们可以匹配空。47         if (help(s, p, indexS, indexP + 2)) {  48             return true;49         }50         51         // 匹配非空的情况,这里不可以跳过p，必须 匹配1个或是多个52         for (int i = indexS; i < sLen; i++) {53             if (!matchChar(s, p, i, indexP)) {54                 return false;55             } else {56                 if (help(s, p, i + 1, indexP + 2)) {57                     return true;58                 }59             }60         }61         62         // 多重匹配之后，余下的字串仍然不可以匹配，则返回失败。63         return false;64     }65     66     // check if the s match p in the index.67     public static boolean matchChar(String s, String p, int indexS, int indexP) {68         return (s.charAt(indexS) == p.charAt(indexP)) || p.charAt(indexP) == '.';69     }70 }

 

SOLUTION2:

稍微重写了一下，思路没有什么大的变化，但是简化了一点点：

我们只需要判断2种情况：

1. 下一个是*的情况，这个时候不需要考虑S长度。因为S为空也是可以的。

2. 下一个不是*，这个统一考虑，当前s必须留下至少一个字符，如果有，继续递归即可。

1 public class Solution { 2     public boolean isMatch(String s, String p) { 3         if (s == null || p == null) { 4             return false; 5         } 6          7         return isMatchRec(s, p, 0, 0); 8     } 9     10     public boolean isMatchRec(String s, String p, int indexS, int indexP) {11         int lenS = s.length();12         int lenP = p.length();13         14         // we get to the end of the string.15         if (indexP == lenP) {16             return indexS == lenS;17         }18         19         // At lease 2 match character left20         if (indexP < lenP - 1 && p.charAt(indexP + 1) == '*') {21             // match 0;22             if (isMatchRec(s, p, indexS, indexP + 2)) {23                 return true;24             }25             26             // we can match 0 or more.27             for (int i = indexS; i < lenS; i++) {28                 // match once or more.29                 if (!isMatchChar(s.charAt(i), p.charAt(indexP))) {30                     return false;31                 }32                 33                 if (isMatchRec(s, p, i + 1, indexP + 2)) {34                     return true;35                 }36             }37             38             // if any of them does not match, just return false.39             return false;40         }41         42         // match current character and the left string.43         return indexS < lenS 44                  && isMatchChar(s.charAt(indexS), p.charAt(indexP)) 45                  && isMatchRec(s, p, indexS + 1, indexP + 1);46     }47     48     public boolean isMatchChar(char s, char p) {49         if (p == '*') {50             return false;51         }52         53         if (s == p || p == '.') {54             return true;55         }56         57         return false;58     }59     60 }

2014.12.28 Redo:

1 public boolean isMatch(String s, String p) { 2         if (s == null || p == null) { 3             return false; 4         } 5          6         return dfs(s, p, 0, 0); 7     } 8      9     public boolean dfs(String s, String p, int indexS, int indexP) {10         int lenS = s.length();11         int lenP = p.length();12         13         // THE BASE CASE:14         if (indexP >= lenP) {15             // indexP is out of range. Then the s should also be empty.16             return indexS >= lenS;17         }18         19         // The first Case: next node is *20         if (indexP != lenP - 1 && p.charAt(indexP + 1) == '*') {21             // p can skip 2 node, and the S can skip 0 or more characters.22             if (dfs(s, p, indexS, indexP + 2)) {23                 return true;24             }25             26             for (int i = indexS; i < lenS; i++) {27                 // the char is not equal.28                 // bug 2: Line 31: java.lang.StringIndexOutOfBoundsException: String index out of range: -129                 if (!isSame(s.charAt(i), p.charAt(indexP))) {30                     return false;31                 }32                 33                 if (dfs(s, p, i + 1, indexP + 2)) {34                     return true;35                 }36             }37             38             // Not any of them can match.39             return false;40         } else {41             // S should have at least one character left.42             if (indexS >= lenS) {43                 return false;44             }45             46             if (!isSame(s.charAt(indexS), p.charAt(indexP))) {47                 return false;48             }49             50             // bug 1: forget ';'51             return dfs(s, p, indexS + 1, indexP + 1);52         }53     }54     55     public boolean isSame(char c, char p) {56         return p == '.' || c == p;57     }

时间复杂度： 2^N

因为，假设P全是a*a*a*这样组成，s = aaaaaaaa 而s的每一个字符都有2种可能：与当前的a*匹配,或者与下一个a*匹配（前一个匹配空），这样假设

s有n个字符，则实际上的复杂度是2^N. 

从下是RUNTIME:

 

SOLUTION3:

记忆化搜索，在SOLUTION 2的基础上，加上记忆矩阵。复杂度为M*N*M。

最后一个m是遇到*时，需要遍历一次string。

1 // solution2: dfs + memory 2     public boolean isMatch(String s, String p) { 3         if (s == null || p == null) { 4             return false; 5         } 6          7         int[][] mem = new int[s.length() + 1][p.length() + 1]; 8          9         // BUG 1: forget to init the memory array.10         // BUG 2: the corner is <=11         for (int i = 0; i <= s.length(); i++) {12             for (int j = 0; j <= p.length(); j++) {13                 mem[i][j] = -1;14             }15         }16         17         return dfsMem(s, p, 0, 0, mem);18     }19     20     public boolean dfsMem(String s, String p, int indexS, int indexP, int[][] mem) {21         int lenS = s.length();22         int lenP = p.length();23         24         if (mem[indexS][indexP] != -1) {25             return mem[indexS][indexP] == 1;26         }27         28         // THE BASE CASE:29         if (indexP >= lenP) {30             // indexP is out of range. Then the s should also be empty.31             mem[indexS][indexP] = indexS >= lenS ? 1: 0;32             return indexS >= lenS;33         }34         35         // The first Case: next node is *36         if (indexP != lenP - 1 && p.charAt(indexP + 1) == '*') {37             // p can skip 2 node, and the S can skip 0 or more characters.38             if (dfsMem(s, p, indexS, indexP + 2, mem)) {39                 mem[indexS][indexP] = 1; 40                 return true;41             }42             43             for (int i = indexS; i < lenS; i++) {44                 // the char is not equal.45                 // bug 2: Line 31: java.lang.StringIndexOutOfBoundsException: String index out of range: -146                 if (!isSame(s.charAt(i), p.charAt(indexP))) {47                     mem[indexS][indexP] = 0;48                     return false;49                 }50                 51                 if (dfsMem(s, p, i + 1, indexP + 2, mem)) {52                     mem[indexS][indexP] = 1;53                     return true;54                 }55             }56             57             // Not any of them can match.58             mem[indexS][indexP] = 0;59             return false;60         } else {61             // S should have at least one character left.62             boolean ret =  indexS < lenS 63                 && isSame(s.charAt(indexS), p.charAt(indexP))64                 && dfsMem(s, p, indexS + 1, indexP + 1, mem);65             66             mem[indexS][indexP] = ret ? 1: 0;67             return ret;68         }69     }

 

SOLUTION 4:

DP:

D[i][j]: 表示string s中取i长度的字串，string p中取j长度字串，进行匹配。

状态转移：

1. j >= 2 && P[j - 1] = *，这时，我们可以选择匹配s中的空字串，或匹配无限个。

k: 在s中匹配的字符的个数

所以转移式是：D[i][j] = D[i - k][j - 2] && isSame(s.charAt(i - k), p.charAt(j - 2))   (k: 1-i)

                                D[i - k][j - 2]  (k = 0) 

2. p最后一个字符不是*

那么首先，s中至少还要有一个字符，然后再匹配一个字符，以及上一级也要匹配即可。

D[i][j] = i >= 1

&& isSame(s.charAt(i - 1), p.charAt(j - 1))

&& D[i - 1][j - 1];

3. j = 0;

 D[i][j] = i == 0;  (p为空，则s也是要为空才可以匹配）

以下是运行时间（LEETCODE这道题目的数据太弱了... orz)，看不出太大的区别。

1 // solution4: DP 2     public boolean isMatch(String s, String p) { 3         if (s == null || p == null) { 4             return false; 5         } 6          7         // bug 2: should use boolean instead of int. 8         boolean[][] D = new boolean[s.length() + 1][p.length() + 1]; 9         10         // D[i][j]: i, j, the length of String s and String p.        11         for (int i = 0; i <= s.length(); i++) {12             for (int j = 0; j <= p.length(); j++) {13                 if (j == 0) {14                     // when p is empth, the s should be empty.15                     D[i][j] = i == 0;16                 } else if (p.charAt(j - 1) == '*') {17                     /*18                         P has at least one node.19                     */20                     21                     // The last node in p is '*'22                     if (j < 2) {23                         // a error: there should be a character before *.24                         //return false;25                     }26                     27                     // we can match 0 characters or match more characters.28                     for (int k = 0; k <= i; k++) {29                         // BUG 3: severe! Forget to deal with the empty string!!30                         if (k != 0 && !isSame(s.charAt(i - k), p.charAt(j - 2))) {31                             D[i][j] = false;32                             break;33                         }34                         35                         if (D[i - k][j - 2]) {36                             D[i][j] = true;37                             break;38                         }39                     }40                 } else {41                     D[i][j] = i >= 1 42                          && isSame(s.charAt(i - 1), p.charAt(j - 1))43                          && D[i - 1][j - 1];44                 }45             }46         }47         48         return D[s.length()][p.length()];49     }

 

SOLUTION 5(DP): 

Date: Sep 14, 2017

简化了DP的逻辑：

D[i][j]:

1. If i == 0 => i==0

2. if (j>=2 && p.charAt(j-1) == '*') => D[i][j-2] || (i>=1 && s[i-1] == p[j-2] && D[i-1][j])

3. s[i-1] == p[j-1] && D[i-1][j-1]

1 class Solution { 2     public boolean isMatch(String s, String p) { 3         int lenS = s.length(); 4         int lenP = p.length(); 5          6         boolean[][] D = new boolean[lenS+1][lenP+1]; 7          8         for (int i = 0; i <= lenS; i++) { 9             for (int j = 0; j <= lenP; j++) {10                 if (j == 0) {11                     D[i][j] = i == 0;12                 } else if (j >= 2 && p.charAt(j-1) == '*') {13                     D[i][j] = D[i][j - 2] || 14                         (i >= 1 && isEqual(s.charAt(i-1), p.charAt(j-2)) && D[i-1][j]);                    15                 } else {16                     D[i][j] = i > 0 && isEqual(s.charAt(i-1), p.charAt(j-1)) && D[i-1][j-1];17                 }18             }19         }20         21         return D[lenS][lenP];22     }23     24     public boolean isEqual(char s, char p) {25         return p == '.' || s == p;26     }27 }

 

GitHub: