Wildcard Matching

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

思路：我们维护两个指针inds和indp，分别代表s和p字符串中当前要比较的位置。

如果s[inds] 等于 p[indp]，或者p[indp]为'?'，则匹配成功，inds和indp分别加一，进行下一次匹配。

如果p[indp]为'*'，则记下当前两个字符串匹配的下标，即s_star = inds，p_star = indp。

当我们遇见*号时，*号可以与0到多个字符进行匹配，因此这里我们从匹配0个开始尝试。即令indp加1，然后开始下一轮的匹配(inds未变，而indp加1了，相当于p字符串里这个*号与s中的0个字符进行了匹配)。

当我们发现上述情况均不成立，即s[inds]和p[indp]匹配失败时，看一下p_star的值是否大于-1（初始值为-1，大于-1说明前面遇见了*号），若大于-1，说明之前有*号，然后我们尝试*号再多匹配一个字符，即我们令inds=++s_star，然后indp=p_star + 1，进行下一次迭代。

若上述条件都不成立，那肯定是匹配不上了，return false。

在实现过程中，我们通过inds < s.size()这个条件来判断迭代是否要结束。而在迭代过程中，我们要时刻保证indp < p.size()。如果在迭代中出现了indp = p.size()，说明s和p是不匹配的。

在迭代结束后，我们不能马上就下定论，因为有可能p串的末尾有多个*号我们没有进行完，而*号可以匹配0个符号，所以我们要考虑到这种情况。这里我们进行一下小处理，只要indp < p.size()且p[indp]='*'，就令indp加一。

最后判断indp是否到了p串的末尾就知道是否匹配了。

 class Solution {

 public:

     bool isMatch(string s, string p) {

         int slen = s.size(), plen = p.size();

         int inds = , indp = ;

         int s_star = -, p_star = -;

         while (inds < slen)

         {

             if (indp < plen && p[indp] == '*')

             {

                 s_star = inds;

                 p_star = indp++;

             }

             else if (indp < plen && (s[inds] == p[indp] || p[indp] == '?'))

             {

                 inds++;

                 indp++;

             }

             else if (p_star > -)

             {

                 inds = ++s_star;

                 indp = p_star + ;

             }

             else return false;

         }

         while (indp < plen && p[indp] == '*')

             indp++;

         return indp == plen;

     }

巴特西

Wildcard Matching - LeetCode

最新文章

热门文章