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

import java.util.*;
public class Solution {

    public boolean match (String str, String pattern) {
        // write code here
        int i = 0, j = 0;
        if(str.length() == 0 && pattern.length() == 0 )
            return true;
        if(str.length() != 0 && pattern.length() == 0)
            return false;
        if(str.length()!=0 && str.charAt(str.length()-1) != pattern.charAt(pattern.length()-1)&&( pattern.charAt(pattern.length()-1) != '.' && pattern.charAt(pattern.length()-1)!= '*'))
            return false;  
        if(str.length() == 0 && pattern.length() == 2 && pattern.charAt(1) == '*')
            return true;
        for(; i < str.length() && j < pattern.length();)
        {//匹配的话就是字符完全相等或者pattern里面有.
            if(str.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '.')
            {
                if(j < pattern.length() - 1 && pattern.charAt(j+1) == '*')
                {
                    if(j < pattern.length() -1 && i < str.length() )
                    {
                        return match(str.substring(i+1), pattern.substring(j)) || match(str.substring(i), pattern.substring(j+2)) || match(str.substring(i+1), pattern.substring(j+2));
                    }
                }else
                {
                    i++;
                    j++;
                }
            }else if(j < pattern.length() - 1 && pattern.charAt(j+1) == '*')
                    {
                    j = j + 2;
                    }else
                        return false; 
        }
        if(i == str.length() && j == pattern.length() || (j == pattern.length() - 2 && pattern.charAt(j+1) == '*') || (j == pattern.length() - 1 && pattern.charAt(j) == '*'))
            return true;
            else
            return false;
    }
}