剑指offer_正则表达式匹配

拼搏现实的明天。 2022-06-09 09:51 164阅读 0赞

/*
    请实现一个函数用来匹配包括'.'和'*'的正则表达式。
    模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。
    在本题中，匹配是指字符串的所有字符匹配整个模式。
    例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。
    
    思路：
    从左到右，逐个匹配判断：
    若*(pattern+1) == '*'，
    	若*pattern == *str，或者*pattern == '.'，那么模式串有三种移动方式：
    		模式串当前字符出现0次，即*表示当前字符出现0次，则当前字符使用下一个模式来匹配,str=str,pattern=pattern+2,如str=a,pattern=a*a;
    		模式串当前字符出现1次，即*表示当前字符出现1次，则匹配下一个字符串,str=str+1,pattern=pattern+2,如str=ab,pattern=a*b;
    		模式串当前字符出现2次或2次以上，即*表示当前字符出现2次或以上，则下一个字符也使用当前模式,str=str+1,pattern=pattern,如str=aa,pattern=a*;
    	若*pattern ！= *str，则只能让*表示当前字符出现0次，则str=str，pattern=pattern+2,如str=ab,pattern=b*ab;
    若*(pattern+1) != '*'，那么，如果当前字符匹配则继续比较下一个字符，如果不匹配则返回false.
    */
    
    class Match
    {
    	public static boolean match(char[] str, char[] pattern)
        {
    		//字符串和模式都为空
            if (str==null||pattern==null)
            {
    			return false;
            }
    
    		//字符串和模式都是空串
    		if (str.length<=0&&pattern.length<=0)
    		{
    			return true;
    		}
    
    		return matchCore(str,0,pattern,0);
        }
    
    	public static boolean matchCore(char[] str,int posStr, char[] pattern, int posPattern)
        {
    		//字符串和模式都到达末尾，匹配成功
    		if (posStr==str.length&&posPattern==pattern.length)
    		{
    			return true;
    		}
    		
    		//字符串未到末尾但模式已到达末尾，匹配失败
    		if (posStr!=str.length&&posPattern==pattern.length)
    		{
    			return false;
    		}
    
    		if (posPattern<pattern.length-1&&pattern[posPattern+1]=='*')//pattern+1为'*'，
    		{
    			//若当前匹配，则有三种可能
    			if (posStr!=str.length&&(str[posStr]==pattern[posPattern]||pattern[posPattern]=='.'))
    			{
    				return matchCore(str,posStr,pattern,posPattern+2)|| //*表示当前字符出现0次，则str=str,pattern=pattern+2;
    					matchCore(str,posStr+1,pattern,posPattern+2)|| //*表示当前字符出现1次，则str=str+1,pattern=pattern+2;
    					matchCore(str,posStr+1,pattern,posPattern); //*表示当前字符出现2次或以上，则str=str+1,pattern=pattern;
    			
    			}else 
    				return matchCore(str,posStr,pattern,posPattern+2); //*表示当前字符出现0次，则str=str,pattern=pattern+2;
    		}
    		
    		//pattern+1不为'*'，若当前匹配则判断下一个字符，否则返回fasle
    	
    			if (posStr!=str.length&&(str[posStr]==pattern[posPattern]||pattern[posPattern]=='.'))
    			{
    				return matchCore(str,posStr+1,pattern,posPattern+1);
    			}
    		
    
    		return false;
    	}
    
    	public static void main(String[] args) 
    	{
    		char[] str={'b','c','b','b','a','b','a','b'};
    		char[] pattern={'.','*','a','*','a'};
    		System.out.println(match(str,pattern));
    	}
    }