正则表达式匹配

public boolean match (String str, String pattern) {
    boolean[][] dp = new boolean[str.length() + 1][pattern.length() + 1];
    dp[0][0] = true;
    // 初始化
    for(int j=1;j<pattern.length()+1;j++)
    {
        if(pattern.charAt(j-1) == '*')
            dp[0][j] = dp[0][j-2];
    }
    for (int i = 1; i < str.length() + 1; i++) {
        for (int j = 1; j < pattern.length() + 1; j++) {
            // 如果i、j字符相同
            // 如果j是'.'，即可以是任意字符 aba ab.
            if (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')
                dp[i][j] = dp[i - 1][j - 1];
            else {
                // 如果j是字母 aba abb
                if (pattern.charAt(j - 1) >= 'a' && pattern.charAt(j - 1) <= 'z')
                    dp[i][j] = false;
                // 如果j是'*'，可以重复前面任意次 abbbb a.*
                else if (pattern.charAt(j - 1) == '*') {
                    int m = i;
                    dp[i][j] = dp[m][j - 2];
                    while (m >= 1 && (str.charAt(m - 1) == pattern.charAt(j - 2) ||
                                      pattern.charAt(j - 2) == '.')) {
                        // 去掉所有和*前面字符相同的字符
                        m = m - 1;
                        dp[i][j] = dp[i][j] || dp[m][j - 2];
                    }
                }
            }
        }
    }
    return dp[str.length()][pattern.length()];
}

import java.util.*;


public class Solution {
    public boolean match (String str, String pattern) {
        // write code here
        int n = str.length(), m = pattern.length();
        boolean[][] dp = new boolean[n + 1][m +
                                            1]; //表示前m个字符和前n个正则是否匹配
        dp[0][0] = true;
        //""和".*" 匹配
        for (int i = 0; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if (pattern.charAt(j - 1) == '*' && j >= 2) {
                    dp[i][j] = dp[i][j - 2];//* 匹配 0 次 对应状态方程f(i,j) = f(i,j - 2)
                    if (isMatch(str, pattern, i, j - 1)) { //匹配至少一次 * 前面的
                        dp[i][j] = dp[i][j] ||
                                   dp[i - 1][j]; // 对应状态方程f(i,j) = f(i,j - 2) || f(i - 1, j)
                    }
                } else {
                    if (isMatch(str, pattern, i, j)) { //匹配 . 或者相同字符 f(i,j) = f(i - 1,j - 1)
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[n][m];
    }

    public boolean isMatch(String s, String p, int i, int j) {
        if (i == 0 || j == 0) return false;
        return s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.';
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        //define
        boolean[][] dp=new boolean[str.length()+1][pattern.length()+1];
        //initialize
        dp[0][0]=true;
        for(int i=1;i<=str.length();i++){
            dp[i][0]=false;
        }
        for(int j=1;j<=pattern.length();j++){
            char c=pattern.charAt(j-1);//长度为j，拿的是index=j-1的字符
            if(c!='*'){dp[0][j]=false;}
            else{
                dp[0][j]=dp[0][j-2];
            }
        }
        //开始状态转移
        for(int i=1;i<=str.length();i++){
            for(int j=1;j<=pattern.length();j++){
                char c1=str.charAt(i-1),c2=pattern.charAt(j-1);
                if(c2=='*'){
                    char c3=pattern.charAt(j-2);
                    if(c3!='.'&&c3!=c1){dp[i][j]=dp[i][j-2];}
                    else{
                        dp[i][j]=dp[i][j-2]||dp[i-1][j];
                    }
                }
                else if(c2=='.'){
                    dp[i][j]=dp[i-1][j-1];
                }
                else{//字母比较
                    if(c1!=c2){dp[i][j]=false;}
                    else{dp[i][j]=dp[i-1][j-1];}
                }
            }
        }
        //return
        return dp[str.length()][pattern.length()];
        
    }
}

    public boolean match (String str, String pattern) {
        int m = str.length();
        int n = pattern.length();
        // 因为最后返回dp[m][n] 表示前m个字符和前n个正则是否匹配 mn可以看作字符串长度或字符个数
        // 所以数组大小必须是m+1 和 n + 1才会有m和n的索引
        boolean[][] dp = new boolean[m + 1][n + 1];
        // base case 空串空正则
        dp[0][0] = true;
        // 注意是小于等于 因为最后输出dp[m][n]
        for(int i = 0; i <= m; i++){
            for (int j = 0; j <= n; j++){
                // 递归计算所有字串和子正则是否匹配
                // 正则为空 除了字符串为空都不匹配
                // 但是字符串为空 正则不为空也是需要通过计算得到的
                if(j == 0)  dp[i][j] = (i == 0 ? true:false);
                // 不为 *
                else{
                    // j一定大于0
                    if(pattern.charAt(j - 1) != '*'){
                        if( i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.'))
                            dp[i][j] = dp[i - 1][j - 1];
                        // 如果i<0 那么就是空字符串和结尾不为*的正则进行匹配那么一定为false 这是空串有正则的一种情况
                        // 如果i>0 但是字符串末尾字符与正则末尾字符不相同且其不为'.' 都是默认值false
                    }else {
                        // 为 * 不管i为什么情况 都可以出现0次
                        // 如果用例正常不会出现j<2的情况
                        if(j >= 2) dp[i][j] |= dp[i][j - 2];
                        if(i > 0 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.'))
                            dp[i][j] |= dp[i - 1][j];
                        // 如果i == 0 走 dp[i][j] |= dp[i][j - 2];
                    }
                }
            }
        }
        return dp[m][n];
    }

import java.util.*;
public class Solution {

    public boolean match (String str, String pattern) {
        // write code here
        int len1 = str.length();
        int len2 = pattern.length();
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;
        // 下面是为了初始化x*x*x*x*这种情况
        for(int j = 2; j <= len2; j++){
            if(pattern.charAt(j - 1) == '*'){
                dp[0][j] = dp[0][j - 2];
            }
        }
        // i和j表示长度
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(pattern.charAt(j - 1) != '*'){
                    if(isMatch(str.charAt(i - 1), pattern.charAt(j - 1))){
                        dp[i][j] = dp[i - 1][j - 1];
                    }else{
                        dp[i][j] = false;
                    }
                }else{
                    // 判断pattern '*'之前的字符是否和str当前字符匹配
                    if(isMatch(str.charAt(i - 1), pattern.charAt(j - 2))){
                        //‘*’之前的字符取0次 || ‘*’之前的字符取多次
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    }else{
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[len1][len2];
    }

    // 判断当前两个字符是否匹配
    private boolean isMatch(char ch1, char ch2){
        if(ch1 == ch2 || ch2 == '.'){
            return true;
        }
        return false;
    }
}

import java.util.*;


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

        str = " " + str;
        pattern = " " + pattern;

        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;

        for (int i = 0; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (j + 1 <= len2 && pattern.charAt(j + 1) == '*') {
                    continue;
                }
                if (pattern.charAt(j) != '*') {
                    dp[i][j] = i >= 1 && j >= 1 && dp[i - 1][j - 1] && (pattern.charAt(j) == '.' ||
                            str.charAt(i) == pattern.charAt(j));
                } else {
                    dp[i][j] = (j >= 2 && dp[i][j - 2]) || (i >= 1 && j >= 1 && dp[i - 1][j] &&
                            (str.charAt(i) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.'));
                }
            }
        }
        return dp[len1][len2];
    }
}

public boolean match (String str, String pattern) {
        // write code here
        // 递归实现正则表达式匹配
        return match(str.toCharArray(), 0, pattern.toCharArray(), 0);
    }
    public boolean match(char[] str, int si, char[] pattern, int pi){
        // 递归结束条件是：如果pattern走完了，chars还没匹配结束，则说明无法匹配成功
        if (pi >= pattern.length){
            return si >= str.length;
        }
        // 如果pattern[pi + 1] =“*”
        if (pi + 1 < pattern.length && pattern[pi + 1] == '*'){
            if (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')){
                boolean ret2 = match(str, si, pattern, pi + 2); // str[si]匹配pattern,匹配到0个字符，那么pi需要向右移动两位
                boolean ret1 = match(str, si + 1, pattern, pi + 2); // str[si]的值与pattern[pi]匹配一次，那么si需要向右移动一位，pi向右移动两位
                boolean ret3 = match(str, si + 1, pattern, pi); // str[si]的值匹配了一个，再匹配下一个，那么pi不动，si需要向右移动一位
                return ret1 || ret2 || ret3 ;
            }else {
                // *前面的值匹配失败，那么si不动，pi需要向右移动两位
                return match(str, si, pattern, pi + 2);
            }
        }
        // 如果str[si]的值和pattern[pi]的值相等或者pattern[pi] =“.”，那么匹配成功，si和pi都向右移动一位
        if (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')){
            return match(str, si + 1, pattern, pi + 1);
        }
        return false;
    }

/**
     * str     pattern
     * 1.   null    null
     * 2.   null    !null   .*
     * 3.   !null   null
     * 4.   !null   !null
     *     1)  . | char    true
     *     2)  .*
     *         a)  取   j不动，i往前走
     *         b)  不取  i不动，j-=2
     */
    public boolean match(String str, String pattern) {
        int n = str.length();
        int m = pattern.length();
        boolean[][] dp = new boolean[n + 1][m + 1];

        dp[0][0] = true;
        for (int i = 2; i <= m; i += 2) {
            if (pattern.charAt(i - 1) == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = false;
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (pattern.charAt(j - 1) == '*') {
                    if (match(str.charAt(i - 1), pattern.charAt(j - 2))) {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && match(str.charAt(i - 1), pattern.charAt(j - 1));
                }
            }
        }
        return dp[n][m];
    }


    private boolean match(char target, char source) {
        return source == '.' || source == target;
    }

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 (pattern.equals("")) {
            if (str.equals(""))
                return true;
            else
                return false;
        }
        boolean res = isMatch(str, str.length()-1, pattern, pattern.length()-1);
        return res;
    }
    
    public boolean isMatch(String str, int i, String pattern, int j) {
        //表示pattern走到头了
        if (j < 0) {
            //原字符串若也到头了，true
            if (ipa < 0)
                return true;
            else
                return false;
        }
        //若当前需要匹配的不是‘*’，则它要么是'.'要么是字符，且必须保证 i>=0, 即原str中还有可用来匹配的字符
        if (pattern.charAt(j) != '*') {
            if (i >= 0 && (pattern.charAt(j) == '.' || pattern.charAt(j) == str.charAt(i)))
                //接着看前面的是否匹配
                return isMatch(str, i-1, pattern, j-1);
            else
                return false;
        }
        //若当前需要匹配的是“*”，则有两种可能，即"*"前面的字符根本用不上，与“*”前面的字符用上了好几次
        else {
            //用不上当前“*”前字符时，直接抛弃pattern当下与前一位，接着匹配余下字符
            boolean no = isMatch(str, i, pattern, j-2);
            //接下来看若需要用“*”与之前字符时
            boolean yes = false;
            //首先要保证str还有可用来匹配的字符，其次看是否满足可匹配的条件
            if (i >= 0 && (str.charAt(i) == pattern.charAt(j-1) || pattern.charAt(j-1) == '.'))
                yes = isMatch(str, i-1, pattern, j);
            //哪条路走得通，都可以
            return yes || no;
        }
    }*/
    
    //动态规划
    public boolean match (String str, String pattern) {
        if (pattern.equals("")) {
            if (str.equals(""))
                return true;
            else
                return false;
        }
        int m = str.length();
        int n = pattern.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (pattern.charAt(j-1) != '*') {
                    if (i > 0 && (pattern.charAt(j-1) == '.' || pattern.charAt(j-1) == str.charAt(i-1)))
                        //接着看前面的是否匹配
                        dp[i][j] = dp[i-1][j-1];
                }
                else {
                    boolean tmp1 = false;
                    boolean tmp2 = false;
                    if (j >= 2) {
                        tmp1 = dp[i][j-2];
                        if (i > 0 && (str.charAt(i-1) == pattern.charAt(j-2) || pattern.charAt(j-2) == '.'))
                            tmp2 = dp[i-1][j];
                    }
                    dp[i][j] = tmp1 || tmp2;
                }
            }
        }
        return dp[m][n];
    }
}