算法:".*"正则表达式实现

算法:".*"正则表达式实现

题目描述:请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"aba"均不匹配*

public class RegularExpression {
    /*
     * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。
     * 模式中的字符'.'表示任意一个字符，
     * 而'*'表示它前面的字符可以出现任意次（包含0次）。
     *  在本题中，匹配是指字符串的所有字符匹配整个模式。
     * 例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
     * */
    public static void main(String[] args) {
        System.out.println("result:" + match("aaa".toCharArray(), "ab*ac*a".toCharArray()));
    }


    public static boolean match(char[] str, char[] pattern) {
        return match2(str, 0, str.length, pattern, 0, pattern.length);
    }

    /*
     *
     * 
     * 思路:这边主要是以pattern为主,考虑一下几种情况发生,使用递归
     * 
     * 考虑几种情况
     * a*
     * .*
     * aa
     * .a
     *
     *
     * */
    public static boolean match2(char[] str, int i, int strLength, char[] pattern, int j, int patternLength) {

        if ((i == strLength) && (j == patternLength)) {
            return true;
        }
        if ((i == strLength) && (j != patternLength)) {
            while (j != patternLength) {
//                考虑什么时候会false
//                aa
//                .a
//
                if ((pattern[j] != '*' &&((j + 1 >= patternLength) || pattern[j + 1] != '*'))) {
                    return false;
                }
                j++;
            }
            return true;
        }
        if ((i != strLength) && (j  == patternLength)) {
            return false;
        }

        if (str[i] == pattern[j] || pattern[j] == '.') {
//            第一个相等 a*或者.*
            if ((j + 1 < patternLength) && pattern[j + 1] != '*') {
//                aa 或者 .a
                return match2(str, i + 1, strLength, pattern, j + 1, patternLength);
            }
            if ((j + 1 < patternLength) && pattern[j + 1] == '*') {
//                a* 或者.*
//                a* 就两种情况  要么 aaaaaa 要么 ''
                return match2(str, i + 1, strLength, pattern, j, patternLength) || match2(str, i, strLength, pattern, j + 2, patternLength);

            }
            if (j + 1 == patternLength) {
//                a结尾,正则表达式已经到最后
                return match2(str, i + 1, strLength, pattern, j + 1, patternLength);
            }
        }else {
//            第一个不等
            if ((j + 1 < patternLength) && pattern[j + 1] == '*') {
//                a* 或者.*
//                a* 就两种情况  要么 aaaaaa 要么 ''
                return match2(str, i, strLength, pattern, j + 2, patternLength);
            }
        }
        return false;

    }
    
    /*
    * 思路:这边主要是想用正向的方式去把所有的方式都解决,考虑一下所有情况
    * */
//    public static boolean match(char[] str, char[] pattern) {
//        if (str.length == 0 && pattern.length == 0) {
//            return true;
//        }
//        if (str.length != 0 && pattern.length == 0) {
//            return false;
//        }
//        if (str.length == 0 && pattern.length != 0) {
//            if (pattern.length > 1 && pattern[1] == '*') {
//                //第二个是*
//                return match("".toCharArray(), String.valueOf(pattern).substring(2).toCharArray());
//            } else {
//                return false;
//            }
//        }
////        下面的情况是 str 和pattern 长度都不为0
////        str 和pattern 都不为0
//        char p1 = pattern[0];
//        if (pattern.length > 1) {
////            pattern 长度大于1位
////            判断是否有*存在
//            char p2 = pattern[1];
//            if (p2 == '*') {
//                if (pattern.length > 2) {
////                    考虑 aaaaaaaa  和a*a*的情况
//                    if (str[0] != p1 && p1 !='.'){
//                        return match(str,String.valueOf(pattern).substring(2).toCharArray());
//                    }
//                    if (pattern[2] == p1) {
//                        int sLength = 0;
//                        int pLength = 0;
//                        int pIndex = 0;
//                        while (sLength < str.length && str[sLength] == str[0]) {
//                            sLength++;
//                        }
//                        for (int i = 0; i < pattern.length; i++) {
//                            if (pattern[i] == p1) {
//                                pLength++;
//                                pIndex ++ ;
//                            } else if (pattern[i] == '*') {
//                                pLength--;
//                                pIndex ++;
//                            } else {
//                                break;
//                            }
//                        }
//                        if (pLength <= sLength) {
//                            return match(String.valueOf(str).substring(sLength).toCharArray(),String.valueOf(pattern).substring(pIndex).toCharArray());
//                        } else {
//                            return false;
//                        }
//                    } else {
////                        这里是 aaa  和 a*b的情况
//                        return match(String.valueOf(str).substring(1).toCharArray(), pattern);
//                    }
//                } else {
//                    //                        这里是 aaa  和 a* 或 b* 或 .*的情况
//                    // pattern.length <=2
//                    if (str[0] == p1){
//                        return match(String.valueOf(str).substring(1).toCharArray(), pattern);
//                    }else {
//                        return false;
//                    }
//                }
//            } else {
//                if (p1 == '.' || p1 == str[0]) {
//                    return match(String.valueOf(str).substring(1).toCharArray(), String.valueOf(pattern).substring(1).toCharArray());
//                } else {
//                    return false;
//                }
//            }
//        } else {
////            pattern 的长度为1
//            if (p1 == '.' || p1 == str[0]) {
//                return match(String.valueOf(str).substring(1).toCharArray(), "".toCharArray());
//            } else {
//                return false;
//            }
//        }
//    }
}