题解 | #正则表达式匹配#

• 如果两个字符串均为空字符串，则直接返回true
• 如果原先的字符串不为空，待匹配的字符串是空的则直接返回false
• 字符串数组pattern开始位置的下一位置为'*'，如果两个字符串开始位置比较，这里匹配存在两种情况，即str字符串是否为空
• ----如果str字符串为空，则pattern向后移动两个字符，继续比较match(str,pattern[2:])
• ----否则如果str字符串不为空则存在三种可能的情况：
•       -----接着如果str[0]=pattern[0]或者pattern[i]=‘.’，例如str=aaa，pattern=.*aa，那么pattern数组中'*'前面字符可以出现任意次，如果出现0次，那么继续匹配match(str,pattern[2:])；如果出现1次，匹配match(str[1:],pattern[2:])，如果出现大于1次，匹配match(str[1:],pattern)
• 字符串数组pattern开始位置的下一位置不为'*'，且两个字符串的开始位置相同或者patter的开始字符为'.'，则直接继续比较后面的字符串match(str[1:],pattern[1:])

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @param pattern string字符串 
# @return bool布尔型
#
class Solution:
    def match(self , str , pattern ):
        # write code here
        if len(str) == 0 and len(pattern) == 0:
            return True
        if len(str) > 0 and len(pattern) == 0:#原字符串不为空，待匹配的字符串为空，直接返回false
            return False
        if len(pattern) > 1 and pattern[1] == '*':
            if len(str) > 0 and (str[0] == pattern[0]&nbs***bsp;pattern[0] == '.'):#两个字符相同或者待匹配的字符为.可匹配成功
                return self.match(str, pattern[2:])&nbs***bsp;self.match(str[1:], pattern[2:])&nbs***bsp;self.match(str[1:], pattern)
            else:
                return self.match(str, pattern[2:])
        if len(str) > 0 and (pattern[0] == '.'&nbs***bsp;pattern[0] == str[0]):
            return self.match(str[1:], pattern[1:])
        return False

• 时间复杂度：程序不断的递归，因此时间复杂度为$O(n^2)$
• 空间复杂度：空间复杂度为$O(1)$

• 待匹配的字符串数组上一位置pattern[j-1]为'*'，如果str[i-1]== pattern[j-2 ]或者pattern[j-2] == '.'，那么pattern数组中'*'前面字符可以出现任意次，则其状态转移方程为$dp[i][j] = dp[i][j - 2] || dp[i - 1][j]$;否则模式的'*'前一位字符与字符串的上个字符不匹配，那么状态转移方程为$dp[i][j]=dp[i-][j-2]$
• 如果模式的前一位字符与字符串的上个字符匹配，即str[i-1]== pattern[j-1 ]或者pattern[j-1] == '.'，状态转移方程$dp[i][j]=dp[i-1][j-1]$

图解

JAVA核心代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
       if (str == null || pattern == null) 
       {
		return false;
	   }
        boolean[][] dp = new boolean[str.length() + 1][pattern.length() + 1];
        dp[0][0] = true;
        int n1=str.length();
        int n2=pattern.length();
        for (int i = 0; i <= n1; i++) 
        {
            for (int j = 1; j <= n2; j++) 
            {
                if (j > 1 && pattern.charAt(j-1) == '*') 
                {
                    if (i > 0 && (str.charAt(i-1) == pattern.charAt(j-2) || pattern.charAt(j-2) == '.')) 
                    {
                        //模式的'*'前一位字符与字符串的上个字符匹配
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    } 
                    else 
                    {
                        //模式的'*'前一位字符与字符串的上个字符不匹配
                        dp[i][j] = dp[i][j - 2];
                    }
                } 
                else if (i > 0 && (str.charAt(i - 1) == pattern.charAt(j-1) || pattern.charAt(j-1) == '.'))
                {
                        //模式的前一位字符与字符串的上个字符匹配
                        dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
       return dp[n1][n2];
    }
}

复杂度分析