# Wildcard Matching ### Source - leetcode: [Wildcard Matching | LeetCode OJ](https://leetcode.com/problems/wildcard-matching/) - lintcode: [(192) Wildcard Matching](http://www.lintcode.com/en/problem/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). Example 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 ~~~ ### 題解1 - [DFS](# "Depth-First Search, 深度優先搜索") 字符串的通配實現。'`?`'表示匹配單一字符，'`*`'可匹配任意多字符串(包含零個)。要匹配的字符串設為`s`, 模式匹配用的字符串設為`p`，那么如果是普通字符，兩個字符串索引向前推進一位即可，如果`p`中的字符是`?`也好辦，同上處理，向前推進一位。所以現在的關鍵就在于如何處理'`*`', 因為`*`可匹配0, 1, 2...個字符，所以遇到`*`時，`s`應該盡可能的向前推進，注意到`p`中`*`后面可能跟有其他普通字符，故`s`向前推進多少位直接與`p`中`*`后面的字符相關。同時此時兩個字符串的索引處即成為回溯點，如果后面的字符串匹配不成功，則`s`中的索引向前推進，向前推進的字符串即表示和`p`中`*`匹配的字符個數。 ### Java ~~~ public class Solution { /** * @param s: A string * @param p: A string includes "?" and "*" * @return: A boolean */ public boolean isMatch(String s, String p) { if (s == null || p == null) return false; if (s.length() == 0|| p.length() == 0) return false; return helper(s, 0, p, 0); } private boolean helper(String s, int si, String p, int pj) { // index out of range check if (si == s.length() || pj == p.length()) { if (si == s.length() && pj == p.length()) { return true; } else { return false; } } if (p.charAt(pj) == '*') { // remove coninuous * while (p.charAt(pj) == '*') { pj++; // index out of range check if (pj == p.length()) return true; } // compare remaining part of p after * with s while (si < s.length() && !helper(s, si, p, pj)) { si++; } // substring of p equals to s return si != s.length(); } else if (s.charAt(si) == p.charAt(pj) || p.charAt(pj) == '?') { return helper(s, si + 1, p, pj + 1); } else { return false; } } } ~~~ ### 源碼分析 其中對`*`的處理和遞歸回溯是這段代碼的精華。 ### 復雜度分析 最壞情況下需要不斷回溯，時間復雜度 O(n!)×O(m!)O(n!) \times O(m!)O(n!)×O(m!), 空間復雜度 O(1)O(1)O(1)(不含棧空間)。 ### Reference - Soulmachine 的 leetcode 題解 -