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

import java.util.*;

public class Solution {

public boolean match (String str, String pattern) {
    // write code here
    ArrayList<String> patterns = splitString2List(pattern);
    return recursion(str, patterns, 0, 0);
}

public ArrayList<String> splitString2List(String pattern) {
    ArrayList<String> patterns = new ArrayList<>();
    for (int i = 0; i < pattern.length(); ) {
        if (i < pattern.length() - 1 && pattern.charAt(i + 1) == '*') {
            patterns.add(pattern.substring(i, i + 2));
            i += 2;
        } else {
            patterns.add(pattern.substring(i, i + 1));
            i++;
        }
    }
    return patterns;
}

public boolean recursion(String str, ArrayList<String> patterns,
                         int sub_str_index, int sub_pattern_index) {
    if(sub_str_index < str.length() && sub_pattern_index >= patterns.size()) return false;
    if(sub_str_index >= str.length() && sub_pattern_index >= patterns.size()) return true;
    for (int i = sub_str_index; i <= str.length(); i++) {
        boolean flag1 = subMatch(str.substring(sub_str_index, i), patterns.get(sub_pattern_index));
        if(!flag1) continue;
        boolean flag2 = recursion(str, patterns, i, sub_pattern_index + 1);
        if (flag2) return true;
    }
    return false;
}

public boolean subMatch(String str, String subPattern) {
    if (".*".equals(subPattern)) {
        return true;
    } else if (".".equals(subPattern) && str.length() == 1) {
        return true;
    } else if (str.equals(subPattern)) {
        return true;
    } else if(subPattern.length() == 2){
        char c = subPattern.charAt(0);
        for (int i = 0; i < str.length(); i++) {
            if (c != str.charAt(i)) return false;
        }
        return true;
    }
    return false;
}

}