wildcard-matching.md

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

分析

跟上一题很类似。

主要是'*'的匹配问题。p每遇到一个'*'，就保留住当前'*'的坐标和s的坐标，然后s从前往后扫描，如果不成功，则s++，重新扫描。

递归版

{% codesnippet "./code/wildcard-matching-1."+book.suffix, language=book.suffix %}{% endcodesnippet %}

迭代版

{% codesnippet "./code/wildcard-matching-2."+book.suffix, language=book.suffix %}{% endcodesnippet %}

相关题目

• Regular Expression Matching