【LeetCode】44. Wildcard Matching解法及注释

Myth丶恋晨 2022-07-26 00:20 41阅读 0赞

44. Wildcard Matching

Implement wildcard pattern matching with support for '?' and '\*'.  
1. '?' Matches any single character.  
2. '\*' Matches any sequence of characters (including the empty sequence).  
3. The matching should cover the entire input string (not partial).  
4. The function prototype should be: bool isMatch(const char \*s, const char \*p)  
<Some examples:>  
isMatch("aa","a") → false  
isMatch("aa","aa") → true  
isMatch("aaa","aa") → false  
isMatch("aa", "\*") → true  
isMatch("aa", "a\*") → true  
isMatch("ab", "?\*") → true  
isMatch("aab", "c\*a\*b") → false

【分析】

此题是一个“通配符”匹配问题，给定两个字符串，判断是否匹配，根据题意：字符串s为不包含通配符的普通字符串，字符串p为包含通配符“\*”和“？”的字符串，我们需要判断的就是字符串p是否与s匹配，因此，我们需要逐次比较两个字符串的字符。

根据题目给出的examples，我们可以得出一些基本规则：(设ps，pp分别为字符串s和p的下标)

1. 如果s\[ps\]==p\[pp\]，直接移动下标(pp++；ps++)，比较下一个位置的字符是否相等；

2. 如果p\[pp\]=='?'，那么无论对应的s\[ps\]是什么字符都为所谓，同1的处理一样；

3. 如果p\[pp\]==‘\*’，本题的难点就来了，‘\*’可以匹配任何字符和字符串，但它究竟该和s中的哪些或哪些字符匹配，我们需要比较后面的字符，举个例子s="abcacc",p="abc\*c"，前三个字符都是匹配的，移动下标即可，当ps=pp=3，即s\[ps\]='a'，p\[pp\]='\*'时，我们并不知道‘\*’该匹配什么字符，只能根据后面的比较结果来决定，我们移动pp到下一位：p\[4\]='c'，与s\[3\]不匹配，因此，‘\*’需要匹配s\[3\]，即使确定s\[3\]由p\[3\]匹配，我们并不能确定p\[3\]='\*'只与s\[3\]匹配，它可以匹配多个字符，因此我们需要保存‘\*’的位置。我们继续移动ps，s\[ps\]=s\[4\]='c'，此时pp回到为3，同上，我们移动pp，p\[pp\]=p\[4\]='c'，两者恰好匹配，同时移动pp，ps，发现s\[5\]！=p\[5\]，这时候，我们需要用到“回溯法”的思想，重新将pp移动到‘\*‘的位置3，ps回溯到上一次已经用’\*‘匹配过的ps=3的位置的下一位，用pp=3中的’\*‘继续匹配ps=4位置的字符，再移动ps。s\[ps\]=s\[5\]与p\[pp\]=p\[3\]比较，p\[3\]='\*',移动pp，比较下一位，发现p\[4\]=s\[5\]，同时移动pp,ps，达到字符串s的末尾，循环比较结束。

4. 循环比较结束后，并不能确定p和s匹配，比如s="abcacc",p="abc\*cd"，我们需要对p进行验证，只有pp同时到达字符串尾端或者p后面剩余的字符全为’\*‘如：s="abcacc",p="abc\*\*\*\*\*\*\*\*",才能形成匹配。

【算法及注释】

class Solution {
    public:
       bool isMatch(string s,string p)
    	{
    		int LS,LP;//求输入字符串的长度，以便特殊情况的处理
    		LS=s.length();
    		LP=p.length();
    
    		if(LS==0&&LP==0)return true;//均为空串，返回true
    		else if(LS==0&&LP!=0)//s为空，p中全部为'*'则匹配，返回true，否则返回false
    		{
    			int i=0;
    			while(p[i]=='*')i++;
    			if(i==LP)return true;//判断p 中是否全部为'*'
    			else return false;
    		}
    		else
    		{
    			int pp,ps;//记录输入字符串的下标
    			pp=ps=0;//初始化
    			int matchIndex=0;//记录待匹配字符的下标
    			int starIndex=0;//记录上一个'*'出现的下标
    			bool flag=false;//标记是否前面出现过'*'
    			while(ps<LS)//循环控制条件，因为我们是用p去匹配s，因此循环以s为主导，p主动去匹配s
    			{
    				if(s[ps]==p[pp]||p[pp]=='?')//最简单的情况，直接移动下标，比较下一位
    				{
    					pp++;
    					ps++;
    				}
    				else if(p[pp]=='*')//出现'*'
    				{
    					flag=true;//标记'*'出现
    					starIndex=pp;//记录‘*’出现的位置下标
    					matchIndex=ps;//记录待匹配S字符串的字符下标
    					pp++;//这时只移动pp，再与s中的字符比较，从而确定前面的'*'如何匹配
    				}
    				else
    				{
    					if(!flag)return false;//如果对应位置的字符不同，前面也没有出现过'*'，说明两者不匹配，返回
    					pp=starIndex;//如果前面出现'*'，将pp“回溯”到'*'出现的位置
    					ps=matchIndex;//ps“回溯”到上一次待匹配的字符的下标，进行匹配
    					ps++;//待匹配的s中的字符匹配后，移动ps到下一个位置，继续判断
    				}
    			}
    			while(p[pp]=='*'&&pp<LP)pp++;//待s中的字符被完全匹配后，再对p中的后续字符进行检验，到达末尾或者后面全为'*'
    			if(p[pp]=='\0')return true;
    			else return false;
    					
    		}	
    	}
    };