Regular Expression Matching

た入场券 2023-06-06 08:09 15阅读 0赞

### 文章目录 ###

*  Regular Expression Matching
 *   *  题目
     *  分析
     *   *  解法1
         *  解法2
     *  代码如下
     *   *  解法1代码
         *  解法2代码

# Regular Expression Matching #

## 题目 ##

Given an input string (`s`) and a pattern (`p`), 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).

**Note:**

*  `s` could be empty and contains only lowercase letters `a-z`.
 *  `p` could be empty and contains only lowercase letters `a-z`, and characters like `.` or `*`.

## 分析 ##

本题就是给你一个字符串`s`和一个匹配模式`p`。其中`s`为空串或者仅仅包含`a-z`之间的字符，`p`为空串或者仅仅包含`a-z`，`.`和`*`这些字符。  
然后要求你给出`p`和`s`是否**完全匹配**。

### 解法1 ###

这道题我使用的是递归的解法，该方法也比较容易想到。但是时间复杂度偏高。网上也有这种方法，他们的代码比我的少很多，有兴趣可以去看看。这里详细给出整个匹配过程，代码量可能有点多。  
这里建立一个私有方法用于递归调用：`private boolean isMatch0(String s, String p, int index1, int index2, int pattern, char ch)`。  
其中：  
`index`和`index2`分别是`s`和`p`的当前下标。  
`pattern`是上一次`p`的匹配模式，为`1`表示`a*`之类的形式，为`2`代表`.*`之类的形式。只有这两种形式可以匹配0个或多个字符。  
当`pattern`为`1`时，`ch`表示`*`前面的字符，否则`ch`为``。

`s`和`p`都是从左到右遍历，在匹配的过程中，有以下几种情况。

*  **如果`pattern`为`2`**  
    即`p`之前为`.*`。  
    那么`s`可以选择匹配该情况，也可以选择不匹配该情况。此时`return isMatch0(s, p, index1 + 1, index2, pattern, ch) || isMatch0(s, p, index1, index2, 0, ' ');`。
 *  **如果`pattern`为`1`**  
    即`p`之前为`a*`，a代表任意`[a-z]`中的一个字符。
    
     *  如果`s[index1] == ch`，那么`s`可以选择匹配，也可以选择不匹配。
     *  如果`s[index1] != ch`，那么`s`只能选择不匹配。
 *  **如果`pattern`为`0`**
    
     *  如果`p[index2]`为`.`且下一个字符时`*`，那么设置`pattern`为`2`，按照上面对应的情况处理。
     *  如果`p[index2]`为`.`且下一个字符不是`*`，那么`s`匹配该字符。**注意：`.`表示匹配且必须匹配任意一个字符**。
     *  如果`p[index2]`为`a-z`之间的任意一个字符，且下一个字符是`*`。那么设置`pattern`为`1`，按照上面对应的情况处理。
     *  如果`p[index2]`为`a-z`之间的任意一个字符，且下一个字符不是`*`。如果`s[index1] == p[index2]`，那么`index1`和`index2`都加1；否则返回`false`。
     *  注意，这里不可能出现`p[index2]`为`*`的情况，都被上面处理了。

### 解法2 ###

解法2采用的是动态规划的解法。  
首先，需要建立一个`boolean`的二维数组`dp`。`boolean[][] = new boolean[s.length() + 1][p.length() + 1]`。

有下面的几种情况：

*  如果`s[i - 1] == p[j - 1]`或者`p[j - 1] == '.'`，那么`dp[i][j] == dp[i - 1][j - 1]`。即如果当前的字符能够匹配，那么就相当匹配不包括当前字符的字串。
 *  此外，如果`p[j - 1] == '*'`。若`dp[i][j - 2] == true`，那么`dp[i][j] = true`；若`dp[i][j - 2] == false`且`s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'`，那么`dp[i][j] = dp[i - 1][j]`。  
    即如果当前`p`的字符为`*`，且`dp[i][j-2]`为`true`，那么`p`当前字符和其前面一个字符不管要不要匹配都是`true`。但如果`dp[i][j-2]`为`false`，那么`p`前一个字符如果和`s`当前字符能够匹配（相同或者`p`的前一个字符为`.`），就相当于匹配`s`前面的子串和`p`当前子串。
 *  其他情况都为`false`。

此外，要先处理p为`a*b*`，`a*b*c*`的情况。即第一行中，若`p`当前字符为`*`，那么`p[0][j] = p[0][j - 2]`。

## 代码如下 ##

### 解法1代码 ###

class Solution { 
        private static final int ANY_NUMBER = 1;  // 任意个相同的字符
    	private static final int ANY_CHARACTER_NUMBER = 2;  // 任意个任意字符
        public boolean isMatch(String s, String p) { 
            return isMatch0(s, p, 0, 0, 0, ' ');
        }
        private boolean isMatch0(String s, String p, int index1, int index2, int pattern, char ch) { 
    		if (index1 == s.length() && index2 == p.length()) {   // s和p都达到边界
    			return true;
    		}
    		if (index2 >= p.length() && pattern <= 0) {   // p到达边界且pattern不是任意字符
    			return false;
    		}
    		if (index1 >= s.length()) {  // s到达边界
    			// p的下两个字符为[a-z.]*
    			while (index2 + 1 < p.length() && p.charAt(index2 + 1) == '*') { 
    				index2 += 2;
    			}
    			if (index2 >= p.length()) return true;
    			else return false;
    		}
    		if (pattern == ANY_CHARACTER_NUMBER) {   // 任意字符
    			return isMatch0(s, p, index1 + 1, index2, pattern, ch) ||  // 匹配该字符
    					isMatch0(s, p, index1, index2, 0, ' ');  // 不匹配该字符
    		} else if (pattern == ANY_NUMBER) {   // 任意个相同的字符
    			if (s.charAt(index1) == ch) {   // 相同
    				return isMatch0(s, p, index1 + 1, index2, pattern, ch) ||  // 匹配该字符
    						isMatch0(s, p, index1, index2, 0, ' ');  // 不匹配该字符
    			} else {   // 不同
    				return isMatch0(s, p, index1, index2, 0, ' ');
    			}
    		} else {   // 其他情况
    			char temp = p.charAt(index2);
    			if (temp == '.') { 
    				if (index2 + 1 < p.length() && p.charAt(index2 + 1) == '*') {   // 下一个字符是*
    					return isMatch0(s, p, index1, index2 + 2, ANY_CHARACTER_NUMBER, ' ');
    				} else {   // 匹配单个字符
    					return isMatch0(s, p, index1 + 1, index2 + 1, 0, ' ');  // 只能匹配
    				}
    			} else if (temp == '*') {   // 该情况不可能发生
    				System.out.println("前面的扫描有问题，这里" + index2 + "不应该扫到*");
    				return false;
    			} else {   // [a-z]
    				if (s.charAt(index1) == temp) {   // 相同
    					if (index2 + 1 < p.length() && p.charAt(index2 + 1) == '*') {   // 下一个字符是*
    						return isMatch0(s, p, index1 + 1, index2 + 2, ANY_NUMBER, temp) ||  // 匹配
    								isMatch0(s, p, index1, index2 + 2, 0, ' ');  // 不匹配
    					} else {   // 下一个字符不是*
    						return isMatch0(s, p, index1 + 1, index2 + 1, 0, ' ');
    					}
    				} else {   // 不相同
    					if (index2 + 1 < p.length() && p.charAt(index2 + 1) == '*') {   // 下一个字符是*
    						return isMatch0(s, p, index1, index2 + 2, 0, ' ');
    					} else {   // 下一个字符不是*
    						return false;
    					}
    				}
    			}
    		}
    	}
    }

### 解法2代码 ###

class Solution { 
        public boolean isMatch(String s, String p) { 
            boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
            dp[0][0] = true;
            // 处理 a*b*之类的情况
            for (int i = 1; i <= p.length(); i++) { 
                if (p.charAt(i - 1) == '*') { 
                    dp[0][i] = dp[0][i - 2];
                }
            }
            
            for(int i = 1; i <= s.length(); i++){ 
                for(int j = 1; j <= p.length(); j++){ 
                    if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')
                        dp[i][j] = dp[i - 1][j - 1];
                    
                    else { 
                        if(p.charAt(j - 1) == '*'){ 
                            if (dp[i][j - 2]){ 
                                dp[i][j] = true;
                            }
                            else if(s.charAt(i - 1) == p.charAt(j - 2) 
                                    || p.charAt(j - 2) == '.'){ 
                                dp[i][j] = dp[i - 1][j];
                            }
                        } 
                    }
                }    
            }
            return dp[s.length()][p.length()];
        }
    }