正则表达式匹配

public class Solution {
    public boolean match(char[] str, char[] pattern) {
        // 记忆化搜索
        cache = new int[str.length + 1][pattern.length + 1];
        return check(str, 0, pattern, 0);
    }
    
    private int[][] cache; // 记忆化搜索存储匹配结果
    private boolean check(char[] str, int x, char[] pattern, int y) {
        if (cache[x][y] != 0) return cache[x][y] == 1;
        if (pattern.length == y) { // 模式串用完
            cache[x][y] = str.length == x ? 1 : -1;
            return str.length == x;
        }
        boolean allMatch; // 全部匹配
        boolean firstMatch = x < str.length && (pattern[y] == '.' || str[x] == pattern[y]); // 首字符匹配
        if (y + 1 < pattern.length && pattern[y + 1] == '*') {
            if (firstMatch) allMatch = check(str, x, pattern, y + 2) || check(str, x + 1, pattern, y);
            else allMatch = check(str, x, pattern, y + 2);
        } else {
            allMatch = firstMatch && check(str, x + 1, pattern, y + 1);
        }
        cache[x][y] = allMatch ? 1 : -1;
        return allMatch;
    }
}

思路

动态规划思想。
eg："abc","ab*.c"。
本质上是利用动态规划思想从后往前遍历。
如：i=2,j=4时，"c"和"c"，true；
i=1,j=3时,"b"和"."匹配，则其结果与i+1,j+1时相同（true）。

代码

    public boolean match(char[] str, char[] pattern) {
        // pattern违背规则
        if (pattern.length != 0 && pattern[0] == '*') return false;
        int i = str.length - 1, j = pattern.length - 1;
        while (i >= 0 || j >= 0) {
            // 字符匹配和pattern为'.'的情况
            if (i >= 0 && j >= 0 && (str[i] == pattern[j] || pattern[j] == '.')) {
                i--;
                j--;
                // pattern为'*'的情况
            } else if (j - 1 >= 0 && pattern[j] == '*') {
                return matchHelper(str, i + 1, pattern, j + 1);
            } else {
                return false;
            }
        }
        return i == -1 && j == -1;
    }

    /**
     * 动态规划计算遇到".w"后的匹配情况
     *
     * @param str     原字符集
     * @param sIndex  从后往前起始位置
     * @param pattern 匹配规则字符集
     * @param pIndex  起始位置
     * @return 是否匹配
     */
    private boolean matchHelper(char[] str, int sIndex, char[] pattern, int pIndex) {
        boolean[][] dp = new boolean[sIndex + 1][pIndex + 1];
        // 从后往前，str='',pattern=''时的情况
        dp[sIndex][pIndex] = true;
        //以下举例str:[abc]和pattern:[abc*]
        for (int i = sIndex; i >= 0; i--) {
            for (int j = pIndex - 1; j >= 0; j--) {
                // 下一位是'*'
                if (j < pIndex - 1 && pattern[j+1] == '*') {
                    // 是否和当前str[i]匹配（eg:i=3即str:'',pattern读到:c*）
                    // 匹配，eg: i=2,j=2,即：
                    // "c"和"c*"匹配结果由"c"和"" || ""和"c*"决定。
                    // 也就是说，碰到*且前面char匹配时，要么跳过"c*"(即*代表0个c），
                    // 要么str继续向后读1位（eg：abccc,abc*），意为*多代表了1个c。
                    if (i != sIndex && (str[i] == pattern[j] || pattern[j] == '.')) {
                        dp[i][j] = dp[i+1][j] || dp[i][j+2];
                    } else
                        //若不匹配，则只能跳过“c*"，此时*代表0个c
                        dp[i][j] = dp[i][j+2];
                    // 若str[i]与pattern[j]匹配，则结果由二者都向后一位后的结果而定
                    // eg: i=0,j=0 此时[abc]和[abc*]，
                    // 其结果等于i=1,j=1时的结果，即[bc]和[bc*]
                } else if (i != sIndex && (pattern[j] == str[i] || pattern[j] == '.')) {
                    dp[i][j] = dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }

    /**
     * 回溯递归进行匹配
     * @param str
     * @param pattern
     * @return
     */
    public boolean match(char[] str, char[] pattern){
        int len_s = str.length, len_p = pattern.length;
        // 判断 str 是否为空的字符数组 
        if (len_s == 0) {
            while (len_p - 2 >= 0 && pattern[len_p - 1] == '*') {
                len_p -= 2;
            }
            if (len_p == 0) {
                return true;
            }else {
                return false;
            }
        }
        // 判断 pattern 字符数组是否为空
        if (len_p == 0) {
            if (len_s == 0) {
                return true;
            }else {
                return false;
            }
        }
        // 开始进行 逻辑判断
        if (len_p == 1 || len_p > 1 && pattern[1] != '*') {
            //if the next character in pattern is not '*'
            if (str[0] == pattern[0] || (len_s > 0 && pattern[0] == '.')) {
                return match(String.valueOf(str).substring(1).toCharArray(), String.valueOf(pattern).substring(1).toCharArray());
            }else {
                return false;
            }
        }else {
            //if the next character is '*'
            if (str[0] == pattern[0] || (len_s > 0 && pattern[0] == '.')) {
                //
                return match(str, String.valueOf(pattern).substring(2).toCharArray())
                        || match(String.valueOf(str).substring(1).toCharArray(), pattern);
            }else {
                return match(str, String.valueOf(pattern).substring(2).toCharArray());
            }
        }
    }

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        Pattern p=Pattern.compile(new String(pattern));
        Matcher m = p.matcher(new String(str));
        return m.matches();

    }
}

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        return match(str, 0, pattern, 0);
    }
  
    //回溯法
    private boolean match(char[] str, int i, char[] pattern, int j) {
       if (str.length <= i && pattern.length - j == 2 && pattern[j+1] == '*') {
         // a* 的情况
         return true;
       } 
       if (i >= str.length && j >= pattern.length) {
         return true;
       }
       if (i >= str.length || j >= pattern.length) {
         return false;
       }
       if (j+1 < pattern.length && pattern[j+1] == '*') {
         if (pattern[j] != str[i] && pattern[j] != '.') { //当前2个不相等, pattern跳到*号后一个
            return match(str, i, pattern, j+2);
         } else {
            if(match(str, i+1, pattern, j)) { //str跳下一个和pattern比
              return true;
            } else {
              return match(str, i, pattern, j+2);
            }
         }
       } else if (j+1 == pattern.length || 
                  (j+1 < pattern.length && pattern[j+1] != '*')) { //字符后面不为*的情况
         if (pattern[j] == str[i] || pattern[j] == '.') {
           return match(str, i+1, pattern, j+1); //两指针后移动，再比较
         } else {
           return false;
         }
       }
       return false;      
    }
}

public class Solution {
    public boolean match(char[] str, char[] pattern){
        int m = str.length;
        int n = pattern.length;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            if (pattern[i - 1] == '*') dp[0][i] = dp[0][i - 2];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (pattern[j - 1] == str[i - 1] || pattern[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pattern[j - 1] == '*') {
                    if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.') {
                        dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j];
                    } else dp[i][j] = dp[i][j - 2];
                }
            }
        }
        return dp[m][n];
    }
}

循环写法虽然代码量长，但是挺简单的，从后往前比较

public class Solution{
    public static boolean match1(char[] str, char[] pattern){
        int len1 = str.length-1;
        int len2 = pattern.length-1;
        //如果str为空数组，则只在pattern为空或者len2==1&&pattern[1]=='*'时返回true
        if(len1==-1){
            if(len2==-1){
                return true;
            }
            if(len2==1&&pattern[1]=='*'){
                return true;
            }
            return false;
        }
        //字符串和模式都不为空
        while(len1>=0 && len2>=0){
            if(pattern[len2]=='*'){
                --len2;
                while(str[len1]==pattern[len2]||pattern[len2]=='.'){
                    --len1;
                    if(len1<0){
                        return true;
                    }
                }
                --len2;
            }
            if(str[len1]==pattern[len2]||pattern[len2]=='.'){
                --len1;
                --len2;
            }
            else if(pattern[len2]=='*'){
                continue;
            }
            else{
                return false;
            }
        }
        if(len1==-1&&len2==-1){
            return true;
        }
        return false;
    }
}

    public boolean match(char[] str, char[] pattern) {
        if (str.length == 0 && pattern.length == 0) {
            return true;
        }
        return matchCore(str, pattern, 0, 0);
    }

    public boolean matchCore(char[] str, char[] pattern, int strIndex, int patIndex) {
        if (strIndex == str.length && patIndex == pattern.length) {
            return true;
        }
        if (strIndex != str.length && patIndex == pattern.length) {
            return false;
        }
        // 下一个是*
        if (patIndex + 1 < pattern.length && pattern[patIndex + 1] == '*') {
            if (strIndex == str.length || str[strIndex] != pattern[patIndex] && pattern[patIndex] != '.') {
                return matchCore(str, pattern, strIndex, patIndex + 2); // 当前不匹配，只能跳过
            } else {
                return matchCore(str, pattern, strIndex + 1, patIndex)
                        || matchCore(str, pattern, strIndex, patIndex + 2); // 当前匹配，可选择是否跳过
            }
        }
        // 下一个不是*
        if (strIndex < str.length && (str[strIndex] == pattern[patIndex] || pattern[patIndex] == '.')) {
            return matchCore(str, pattern, strIndex + 1, patIndex + 1);
        } else {
            return false;
        }
    }

import java.util.*;
public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        String p = new String(pattern);
        String s = new String(str);
        if(s.matches(p)){
            return true;
        }
        return false;
    }
}

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        String s="",reg="";
        int i;
        for(i=0;i<str.length;i++){
            s=s+str[i];
        }
        for(i=0;i<pattern.length;i++){
            reg=reg+pattern[i];
        }
        return s.matches(reg);
    }
}

 * 思路：找出重点关注的地方分情况讨论
 * ∵ .表示任意字符，所以当模式中的某个字符为.或和字符串中的某字符相等时则匹配，进入下一个字符比较
 * 重点考虑*
 * 一般情况：
 * 当第二个字符为*时(第一个字符为*没有意义，划分问题规模)，可以选择三种情况
 *
 * 如果str第一个字符与pattern第一个字符相同或者pattern第一个字符为.，此时*和前面的字符匹配
 * 第一种：模式向后移动2个字符，字符串向后移动1个字符，继续匹配(比如aaa和a*a*a)
 * 第二种: 模式不移动，字符串向后移动一位，继续匹配* (比如aaa和a*)
 * 第三种：模式向后移动2个字符，*表示前面字符为0，相当于忽略*和前面的字符，字符串不移动(比如aaa和a*a*a*a)
 *
 * 如果str第一个字符与pattern第一个字符不相同，此时*和前面的字符不匹配
 * 模式向后移动两位，字符串向后移动一位，比较下一位，(比如aaa和b*a*b)
 *
 * ========================
 * 如果第二个字符不为*
 * 当第一个字符一样，可能匹配成功或者失败，进入递归
 * 如果第一个字符不一样，则必定失败(为*可以表示前一个字符出现0次)
 *========================
 * 找出base case(何时才算匹配成功)：
 * 当str和pattern都走到尾，表示pattern匹配str成功
 * 当str未走到尾，pattern已经走到尾，此时pattern匹配str失败，str还有剩余字符未匹配
 * 当str走到尾，pattern未走到尾，或str和pattern都未走到尾，此时可能匹配成功，也可能失败，进入一般情况。
 *
 */
 public class Solution {
    public  boolean match(char[] str, char[] pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        return matchCore(0, str, 0, pattern);
    }

    private  boolean matchCore(int strIndex, char[] str, int patternIndex, char[] pattern) {
        if (strIndex == str.length && patternIndex == pattern.length) {
            return true;
        }
        if (strIndex != str.length && patternIndex == pattern.length) {
            return false;
        }
        // 注意保证数组下标不越界
        // 第二个字符为*
        if ((patternIndex + 1) < pattern.length && pattern[patternIndex + 1] == '*') {
            if ((strIndex < str.length && str[strIndex] == pattern[patternIndex]) ||
                    (strIndex < str.length && pattern[patternIndex] == '.')) {
                return matchCore(strIndex, str, patternIndex + 2, pattern)
                        || matchCore(strIndex + 1, str, patternIndex + 2, pattern)
                        || matchCore(strIndex + 1, str, patternIndex, pattern);
            } else { // 第一个字符不匹配
                return matchCore(strIndex, str, patternIndex + 2, pattern);
            }
        }
        if ((strIndex < str.length && pattern[patternIndex] == str[strIndex])
            || (strIndex < str.length && pattern[patternIndex] == '.')) { // 第二个字符不为*,第一个字符匹配
               return matchCore(strIndex + 1, str, patternIndex + 1, pattern);
        }
        return false;
    }
}

public class MatchPattern {
    public boolean match(char[] str, char[] pattern)
    {
    	if(str == null || pattern == null)
    		return false;
    	
    	return matchCore(str,0,pattern,0);
        
    }
    
    private boolean matchCore(char[] str,int strIndex,char[] pattern ,int patternIndex){
    	if(strIndex == str.length && patternIndex == pattern.length)
    		return true;
    	if(strIndex < str.length && patternIndex == pattern.length)
    		return false;
    	
    	if(patternIndex + 1< pattern.length  && pattern[patternIndex + 1] == '*'){
    		if((strIndex < str.length && pattern[patternIndex] == '.')
    			||(strIndex < str.length && pattern[patternIndex] == str[strIndex])){
    			return matchCore(str,strIndex,pattern,patternIndex + 2)
    					||matchCore(str,strIndex+1,pattern,patternIndex + 2)
    					||matchCore(str,strIndex+1,pattern,patternIndex);
    		}
    		else{
    			return matchCore(str,strIndex,pattern,patternIndex + 2);
    		}
    	}
    	
    	if((strIndex < str.length && patternIndex < pattern.length &&  str[strIndex] == pattern[patternIndex]) 
    			|| (strIndex < str.length && patternIndex < pattern.length && pattern[patternIndex]== '.')){
    		return matchCore(str,strIndex + 1,pattern,patternIndex + 1);
    	}
    	return false;
    }
}

//动态规划解法
public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        boolean[][] dp;
        int i, j, ls, lp;

        ls = str.length;
        lp = pattern.length;
        dp = new boolean[lp+1][ls+1];
        dp[0][0] = true;
        for(i = 0; i < lp; i++)
            if(pattern[i] == '*')
                dp[i+1][0] = dp[i-1][0];
        for(i = 0; i < lp; i++){
            for(j = 0; j < ls; j++){
                if(pattern[i] == '*')
                    dp[i+1][j+1] = dp[i-1][j+1] || dp[i][j+1] || (str[j] == pattern[i-1] || pattern[i-1] == '.') && dp[i+1][j];
                else if(pattern[i] == '.' || pattern[i] == str[j])
                    dp[i+1][j+1] = dp[i][j];
                else
                    dp[i+1][j+1] = false;
            }
        }
        return dp[lp][ls];
    }
}

public class Solution {
    public boolean match(char[] str, char[] pattern){
        if(str == null || pattern == null) return false;
        if(str.length == 0){
            if(pattern.length == 0 || (pattern.length == 2 && pattern[1] == '*')){
                return true;
            }else{
                return false;
            }
        }
        if(pattern.length == 0)return false;
        int i = 0;
        int j = 0;
        while(i < str.length){
            if(j == pattern.length - 1){
                if(i == str.length - 1 && (str[i] == pattern[j] || pattern[j] == '.')){
                    return true;
                }else{
                    return false;
                }
            }
            if(j > pattern.length - 1) return false;
            if(pattern[j + 1] == '*'){
                int index = i;
                // 记录回退数量，管理这样的"a*a"的匹配
                int back = 0;
                int point = j + 1;
                while(++point <= pattern.length - 1 && ((index + 1 < str.length && str[index + 1] == pattern[j]) || index + 1 == str.length)){
                    if(pattern[point] == pattern[j]){
                        back++;
                        if(point + 1 <= pattern.length - 1 && pattern[point] == '*')back--;
                    }
                }
                // 单独处理"."的回退问题
                while(++point <= pattern.length - 1 && pattern[j] == '.'){
                    back++;
                    if(point + 1 <= pattern.length - 1 && pattern[point] == '*')back--;
                }
                while(index < str.length && (str[index] == pattern[j] || pattern[j] == '.')){
                    index++;
                }
                index-=back;
                if(index == str.length && j + 1 == pattern.length - 1)return true;
                if(j + 1 == pattern.length - 1)return false;
                if(index == str.length)return false;
                j+=2;
                i = index;
            }else{
                if(str[i] != pattern[j] && pattern[j] != '.')return false;
                i++;
                j++;
            }
        }
        if(j + 1 == pattern.length - 1 && pattern[j + 1] == '*')return true;
        return false;
    }
}

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        String string = new String(str);
        String regex = new String(pattern);
        return string.matches(regex);
    }
}