leetcode 44. Wildcard Matching （需要好好想一下）

ゞ浴缸里的玫瑰 2022-06-09 10:17 134阅读 0赞

Implement wildcard pattern matching with support for ‘?’ and ‘\*’.

‘?’ Matches any single character.  
‘\*’ Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

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

就是匹配字符串。

这道题不会做，我是参考网上答案做得，我知道应该用回溯去做，但是暂时想不清楚怎么做。

先参考这份代码吧！？

public class Solution 
    {
        // http://blog.csdn.net/u012848330/article/details/52596618
    
        /*
         *  超时原因在于即便使用了带记录的递归，对于p上的每一个'*'，依然需要考虑'*' 匹配之后字符的所有情况，
         *  比如p = "c*ab*c"，s = "cddabbac"时，遇到第一个'*'，我们需要用递归处理p的剩余部分"ab*c" 和s的
         *  剩余部分"ddabbac"的所有尾部子集匹配。也就是："ab*c"和"ddabbac"，"ab*c" 和"dabbac"的匹配，
         *  "ab*c" 和"abbac"的匹配，... ，"ab*c" 和"c"的匹配，"ab*c" 和"\0"的匹配。
    
            遇到第二个'*'，依然如此。每一个'*'都意味着p的剩余部分要和s的剩余部分的所有尾子集匹配一遍。
            然而，我们如果仔细想想，实际上，当p中'*'的数量大于1个时，我们并不需要像上面一样匹配所有尾子集。
            依然以 p = "c*ab*c"，s = "cddabbac"为例。
             对于p = "c*ab*c"，我们可以猜想出它可以匹配的s应该长成这样： "c....ab.....c"，省略号表示0到
             任意多的字符。我们发现主要就是p的中间那个"ab"比较麻烦，一定要s中的'ab'来匹配，因此只要s中间
             存在一个"ab"，那么一切都可以交给后面的'*'了。
    
              所以说，当我们挨个比较p和s上的字符时，当我们遇到p的第一个'*'，我们实际只需要不断地在s的剩余部分找
                和'ab'匹配的部分。
    
                换言之，我们可以记录下遇到*时p和s的位置，记为presp和press，然后挨个继续比较*(++p)和*(++s)；
                如果发现*p != *s，就回溯回去，p = presp，s = press+1, ++press；直到比较到末尾，或者遇到了
                下一个'*'，如果遇到了下一个'*'，说明 "ab"部分搞定了，下面的就交给第二个'*'了；如果p和s都到末尾了，
                那么就返回true；如果到末尾了既没遇到新的'*'，又还存在不匹配的值，press也已经到末尾了，那么就返
                回false了。
    
                这样的思路和上面的递归比起来，最大的区别就在于：
    
                遇到'*'，我们只考虑遇到下一个'*'前的子问题，而不是考虑一直到末尾的子问题。从而避免大量的子问题计算。
    
                我们通过记录 presp和press，每次回溯的方法，避免使用递归。
         * */
    
    
        public boolean isMatch(String s, String p) 
        {
            //遍历下标
            int indexS=0,indexP=0;
    
            //记录*的位置
            int wildIndexS=0,wildIndexP=0;
    
            //是否需要回溯
            boolean backStrack=false;
    
            while(indexS < s.length())
            {
                if(indexP==p.length())
                {
                    //遍历到最后，无法回溯，false
                    if(backStrack==false)
                        return false;
                    //遍历到最后，遇到万能符，true
                    else if(p.charAt(p.length()-1)=='*')
                        return true;
                    else
                    {
                        //回溯，P回到wildP位置，S可以跳过wildS+1的位置，因为wildS是匹配不成功的
                        indexP=wildIndexP;
    
                        indexS=wildIndexS+1;
                        wildIndexS++;
                    }
                }
    
                //遇到 ？ 下标同时移动
                if(p.charAt(indexP)=='?')
                {
                    indexP++;
                    indexS++;
                //遇到 * ，记录回溯位置，修改回溯标志
                }else if(p.charAt(indexP)=='*')
                {
                    //回溯的位置是*的下一个位置
                    wildIndexP=indexP+1;
                    indexP++;
    
                    //对于s，记录当前的位置就可以了，因为要对当前的位置开始匹配
                    wildIndexS=indexS;
                    backStrack=true;
                }else
                {
                    //遇到相同的字符，下标移动
                    if(p.charAt(indexP) == s.charAt(indexS))
                    {
                        indexP++;
                        indexS++;
    
                    //可以回溯，直接回溯
                    }else if(backStrack)
                    {
                        //不可以回溯，
                        indexP=wildIndexP;
    
                        indexS=wildIndexS+1;
                        wildIndexS++;
                    }else
                        return false;
                }
    
            }
    
            //这个不太懂
            while(indexP < p.length() && p.charAt(indexP)=='*')
            {
                indexP++;
                if(indexP==p.length())
                    break;
            }
    
            return indexP==p.length();
    
    
        }
    }