正则表达式匹配

lass Solution {
public:
    bool match(string str, string pattern) {
        // write code here
        int dp[str.size() + 1][pattern.size() + 1];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1; // 以i，j结尾的字符串
        for(int i=0; i<=str.size(); i++)
            for(int j=1; j<=pattern.size(); j++) {
                if(pattern[j-1] == '*' && j - 2 >= 0 && pattern[j-2] != '*') {
                    dp[i][j] = dp[i][j-2]; // 匹配零次
                    if(i && (pattern[j-2] == str[i-1] || pattern[j-2] == '.'))
                        dp[i][j] = dp[i][j] || dp[i-1][j-2] || dp[i-1][j]; // 匹配一次或者多次
                }
                else if(i && (pattern[j-1] == str[i-1] || pattern[j-1] == '.'))
                    dp[i][j] =  dp[i-1][j-1];
//                 cout << i << " " << j << " " << dp[i][j] << endl;
            }
        return dp[str.size()][pattern.size()];
    }
};

#正则表达式匹配
#请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，
#而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。
#例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# @param str string字符串 
# @param pattern string字符串 
# @return bool布尔型

#实现了两个匹配函数分别用于匹配.和*,总匹配函数按照从后往前的方式来进行
#总匹配函数中考虑了匹配完成后pattern有剩余的各种情况，包括剩余.，剩余的是还可以匹配的字符的情况。
#其中剩余的是还可以匹配的字符这种情况比较头大，因为我们从后往前匹配过程中肯定是尽量多匹配，
#这样就容易造成这样的情况：aaabac   ab*a*ac，其实pattern中第一个a是可以和str中第一个a匹配的，但是我们
#从后往前容易使得第二个*把a全部匹配了，这样就让pattern剩余了ab*,所以需要我们设计对剩余段的处理方式。我的处理思路是这样的
#如果temp也就是a*匹配次数超过了1次，说明它多匹配了，而pattern剩下的部分用*消除后还剩下a，说明pattern中
#剩下的这个a是可以可str中被a*匹配掉的a匹配的，如果剩下a的个数小于等于temp-1，就可以等价一下输出True
#如果temp=1，说明a*只匹配了一个str中的a，如果pattern中还多余元素，那么就说明匹配不了，输出False
class Solution:
    def match(self , str , pattern ):
        #总匹配函数，按照从后往前的方式匹配
        #题目中有".*"的形式，而且*的存在也使得从后往前匹配更加合理
        h=len(pattern)-1
        i=len(str)-1
        if i+1==0:
            if h+1==0&nbs***bsp;(h+1==2 and "*" in pattern):
                return True
            return False
        if h+1==0:
            return False
        while i>=0:
            if str[i]==pattern[h]:
                h-=1
                i-=1
                continue 
            elif pattern[h]==".":
                if self.matchpoint(str[:i+1])==1:
                    h-=1
                    i-=1
                    continue 
                else:
                    return False
            elif pattern[h]=="*":
                if h==0:
                    return False
                temp=self.mathstar(pattern[:h],pattern[h-1],str[:i+1])
                if temp==h+1:
                    return True
                elif temp==0:
                    h-=2
                    continue 
                elif temp>0:
                    h-=2
                    i-=temp
                if i<0 and h>0:
                    if h>0:#处理这种情况：pattern已经可以从后往前将str匹配完毕了，但是pattern还有一部分剩余
                    #if后程序段都是未来处理这剩下的一段的。
                        numofstars=0
                        for i in pattern[h::-1]:
                        #for相当于用pattern剩下这部分中的“*”消除掉“*”前面的字母
                            if i=="*":
                                numofstars+=1
                            else:
                                numofstars-=1
                            if numofstars==0:
                                return True
                        else:#如果还有剩余的字母，“*”无法消去，那么看它们是否是和str[0]相同。
                            if time==1:#如果time，即使它们和str[0]相同，也是多余出来的
                                return False
                            for i in range(-numofstars):
                                if pattern[i]!=str[0]:
                                    return False 
                            if -numofstars<=time-1:
                                return True
            else:
                return False
                return True
        return False if h<-1&nbs***bsp;(h>=0 and pattern[h]!=".") else True
    def mathstar(self,pattern,cp,target):
        time=0#在*的加持下cp和str中字符匹配次数
        flag=len(target)
        if cp==".":#如果和*号搭配的是.号
            if pattern[0]==target[0]:
                return flag+1#将flag+1作为全部匹配成功的标识
            elif pattern[0]==".":
                return flag+1
            elif pattern[1]=="*":
                return flag+1
            else:
        #如果pattern开头和str相等，则无脑输出True，否则查看pattern头是否可以构成 #*的形式或.的形式
        #如果pattern做不到头和str匹配，则输出False
                return -1
        elif cp!=target[flag-1]:
            return 0
        elif cp==target[flag-1]:
            for i in range(flag-1,-1,-1):
                if cp!=target[i]:
                    return time
                time+=1
            for i in pattern[-2::-1]:
                if cp==i:
                    time-=1
                else:
                    break
            return time
        elif cp=="*":
            if len(pattern)==1:
                return False
            return self.matchstar(pattern[:-1], pattern[-2], target)      
    def matchpoint(self,target):
        #"."匹配函数
        if len(target)!=0:
            return 1
        else:
            return -1
    def dealwithPattern(self,pattern):
        #处理Pattern的函数，这个函数在现在的解法中没有使用。
        for i in range(len(pattern)):
            if pattern[i]=="*":
                pattern=pattern.replace(pattern[i-1]+"*",pattern[i-1].upper(),1)
        return pattern

    public boolean match (String str, String pattern) {
        if (pattern.length() == 0) {
            return str.length() == 0;
        }
        // 一对一匹配 或 .
        boolean match = (str.length() > 0 && (str.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '.'));
        // 有*
        if (pattern.length() > 1 && pattern.charAt(1) == '*') {
            // 0个 || 多个
            return match(str, pattern.substring(2)) || (match && match(str.substring(1), pattern));
        }
        // 无*
        else {
            return match && match(str.substring(1), pattern.substring(1));
        }

    }

偷懒了

import java.util.regex.*;
public class Solution {
    public boolean match (String str, String pattern) {
        return Pattern.matches(pattern, str);
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        char[] strings = str.toCharArray();
        char[] patterns = pattern.toCharArray();
        if (str == null || pattern == null) {
            return false;
        }
        int strIndex = 0;
        int patternIndex = 0;
        return matchCore(strings, strIndex, patterns, patternIndex);
    }

    public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
        // 有效性检验：str到尾，pattern到尾，匹配成功
        if (strIndex == str.length && patternIndex == pattern.length) {
            return true;
        }
        // pattern先到尾，匹配失败
        if (strIndex != str.length && patternIndex == pattern.length) {
            return false;
        }
        // 模式下一位是*，且字符串当前位跟模式当前位匹配,分3种匹配模式；如不匹配，模式后移2位
        // 模式下一位为'*'
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
            // 字符串当前位与模式当前位匹配
            if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                    || (pattern[patternIndex] == '.' && strIndex != str.length)) {
                        // 模式后移2，视为x*匹配0个字符
                return matchCore(str, strIndex, pattern, patternIndex + 2)
                        // 视为模式匹配1个字符
                        || matchCore(str, strIndex + 1, pattern, patternIndex + 2)
                        // *匹配1个，再匹配str中的下一个
                        || matchCore(str, strIndex + 1, pattern, patternIndex);
            // 字符串当前位与模式当前位不匹配
            } else {
                return matchCore(str, strIndex, pattern, patternIndex + 2);
            }
        }
        // 模式下一位不是*，且字符串当前位跟模式当前位匹配，则都后移1位，否则直接返回false
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                || (pattern[patternIndex] == '.' && strIndex != str.length)) {
            return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
        }
        return false;
    }
}

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Solution {
    public boolean match (String str, String pattern) {
        Pattern p = Pattern.compile(pattern);
        Matcher matcher = p.matcher(str);
        return matcher.matches();
    }
}

class Solution:
    def match(self, str: str, pattern: str) -> bool:
        m = len(str)
        n = len(pattern)
        dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]
        dp[m][n] = True
        for i in range(m, -1, -1):
            for j in range(n - 1, -1, -1):
                isMatch =  i < len(str) and (str[i] == pattern[j]&nbs***bsp;pattern[j] == ".")
                if j + 1 < len(pattern) and pattern[j + 1] == "*":
                    dp[i][j] = (isMatch and dp[i + 1][j])&nbs***bsp;dp[i][j + 2]
                else:
                    dp[i][j] = (isMatch and dp[i + 1][j + 1])
        return dp[0][0]

import java.util.*;
import java.util.regex.Pattern;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        return Pattern.matches(pattern, str);
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        if(pattern.size()==0&&str.size()==0)
            return true;
        else if(pattern.size()==0)
            return false;
        if(pattern[1]!='*')
        {
            if(str[0]==pattern[0]||(str[0]!='\0'&&pattern[0]=='.'))
                return match(str.substr(1), pattern.substr(1));
            else
                return false;
        }
        else
        {
            if(str[0]==pattern[0]||(str[0]!='\0'&&pattern[0]=='.'))
                return match(str.substr(1), pattern)||match(str, pattern.substr(2));
            else
                return match(str, pattern.substr(2));
        }
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // 时间复杂度O(MN)，空间复杂度O(MN)
        bool dp[str.size() + 1][pattern.size() + 1];
        dp[0][0] = true;
        for (int i = 1; i <= str.size(); ++i) dp[i][0] = false;
        for (int j = 1; j <= pattern.size(); ++j) {
            if (j >= 2 && pattern[j - 1] == '*') dp[0][j] = dp[0][j - 2];
            else dp[0][j] = false;
        }
        for (int i = 1; i <= str.size(); ++i) {
            for (int j = 1; j <= pattern.size(); ++j) {
                if (pattern[j - 1] != '*' && (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.'))
                    dp[i][j] = dp[i - 1][j - 1];
                else if (j >= 2 && pattern[j - 1] == '*') {
                    if (str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.')
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    else dp[i][j] = dp[i][j - 2];
                }
                else dp[i][j] = false;
            }
        }
        return dp[str.size()][pattern.size()];
    }
};

import re


class Solution:
    def match(self, str: str, pattern: str) -> bool:
        # write code here
        m = re.match(pattern, str)
        if m:
            return m.group() == str
        return False