正则表达式匹配

思路：就是分类讨论，把所有可能出现的情况列出来然后问题就迎刃而解了~

解决方法： 两个字符数组各自维护一个指针，表示当前比较到的数组下标

大体上分为两种大情况：
当前比较的字符的下一个是*

（1）这种情况下，假设当前i,j都等于0，所以str[i] = 'a',pattern[j] = '.'
因为.可以表示任何一个字符，所以很明显这种情况下，str[i]==str[j]，因为pattern接下来一个字符是，它可以表示它前面的字符有多少个，那么现在这种情况下，因为str[i]==str[j]，所以表示至少有一个a，为什么是至少呢？我们不能确定str的下一个是否还是a，如果是的话我们肯定是想要表示，有2个a的，所以此时我们i+1，跳到下一个位置，与原来的pattern进行比较。

（2）这种情况下，跟（1）不同的是，假如pattern如图所示，那么要是按照（1）方式，i+1，那么此时假设.表示有2个a，与str的两个a相匹配了，str接下来的字符为b，pattern接下来的字符为a，a!=b,那么此时就可以确定两个字符串不想等了吗？肯定不是的。我们看pattern，它比较特殊，除了.，后面跟str一模一样，所以我们肯定是想.表示前面有0个字符，那么剩下后面的aabce不就跟str相等了吗？
所以此时我们就得j+2，直接跳过当前字符和，比较后面的。

（3）这种情况下，我们则需要将.表示成1个a，然后i+1，j+2，比较下一个字符（可以跟上面一样分析）

当前比较的字符的下一个不是*

这种情况下很简单，直接比较两个指针指向的位置是否相等，相等i++，j++，不想等直接返回false

public boolean match(char[] str, char[] pattern)
    {
        return matchStr(str,0,pattern,0);
    }


    public boolean matchStr(char[] str,int i,char[] pattern, int j){
         //当两个字符数组都走完了，那么就表示相等了，因为如果比较过程中不想等会直接返回false
        if(str.length == i && pattern.length == j)
            return true;
        //str没走完，但是pattern走完了，此时肯定是不想等的
        if(str.length != i && pattern.length == j)
            return false;

        boolean flag = false;
        if(j < pattern.length-1 && pattern[j+1] == '*')
            flag = true;  //用来标记pattern的当前字符的下一个是不是*号
        if(flag){
            if(i < str.length && (str[i] == pattern[j] || pattern[j] == '.'))
                //对应是*号的三种情况
                return matchStr(str,i+1,pattern,j) || matchStr(str,i+1,pattern,j+2) || matchStr(str,i,pattern,j+2);
            else  
                return matchStr(str,i,pattern,j+2); // 当前位置字符都不相等了，肯定直接pattern跳两个
        }else{
            // 对应上面不是*号的情况
            if(i < str.length && (str[i] == pattern[j] || pattern[j] == '.')){
                return matchStr(str,i+1,pattern,j+1);
            }
            return false;
        }   
    }