【leetcode】44. 通配符匹配（wildcard-matching）（BFS）[困难]

链接

https://leetcode-cn.com/problems/wildcard-matching/

耗时

解题：4.5 h
题解：36 min

题意

给定一个字符串（s）和一个字符模式（p） ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

思路

以 p 为行 s 为列，构建一个 p.size() * s.size() 的矩阵，矩阵中 位置 (i,j) 表示：s[0:i] 和 p[0:j] 可以匹配，那么问题将转化为是否可以从位置 (0,0) 走到 位置 (p.size()-1, s.size()-1)。
因为字符串中 ** 与 * 的意义相同，并且还会对规则的实现造成影响，所以首先改造 p，将 p 中连续的多个 * 变为一个。
寻路用的是 BFS，如果 p 的首字符 p[0] 为 ‘?’ 或 ‘*’ 或者与 s[0] 相等，则将 (0,0) 入队，然后开始 BFS。

1. 如果当前位置的 p 字符为 ‘*’，则可以向右走（即匹配对应 s 位置的字符）。如果这个 ‘*’ 是 p 第一个字符，并且 p 下面的字符为 ‘?’ 或者与 s[0] 相等，那么还可以向下走（即 ‘*’ 匹配空字符串）。
2. 如果当前位置的下一个 p 字符为 ‘*’，那么可以直接向下走到达 ‘*’ 的位置（即 ‘*’ 匹配空字符串）。
3. 当然如果当前位置 (i,j) 右下对应的 p[i+1] 为 ‘?’ 或者与 s[j+1] 相等，则自然可以走到右下的位置。

还使用了记录数组来记录走过的位置，防止多次访问同一个位置，优化运行时间。

时间复杂度：最坏情况下每个位置都要入队，即 O ( p . s i z e ( ) ∗ s . s i z e ( ) ) O(p.size() * s.size()) O(p.size()∗s.size())

AC代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int p_num = p.size();
        int s_num = s.size();
        if((p_num == 0 || p == "*") && s_num == 0) return true;
        if((p_num == 0 && s_num != 0) || (p_num != 0 && s_num == 0)) return false;

        vector<vector<bool>> vis(p_num, vector<bool>(s_num, false));
        queue<pair<int, int>> q;
        
        string _p;
        for(int i = 0; i < p_num; ++i) {
            if(p[i] == '*' && !_p.empty() && _p.back() == '*') continue;
            _p += p[i];
        }
        p = _p;
        p_num = p.size();
        
        if(p[0] == '*' || p[0] == '?' || s[0] == p[0]) {
            q.push(make_pair(0, 0));
        } 
        while(!q.empty()) {
            pair<int, int> now = q.front();
            q.pop();
            if(vis[now.first][now.second]) continue;
            vis[now.first][now.second] = true;
            // goal
            if(now.first == p_num-1 && now.second == s_num-1) {
                return true;
            }
            // transfer
            if(p[now.first] == '*') {
                if(now.first == 0 && now.first+1 < p_num && (p[now.first+1] == '?' || p[now.first+1] == s[now.second])) {
                    q.push(make_pair(now.first+1, now.second));
                }
                if(now.second+1 < s_num) {
                    q.push(make_pair(now.first, now.second+1));
                }
            }
            if(now.first+1 < p_num && p[now.first+1] == '*') {
                q.push(make_pair(now.first+1, now.second));
            }
            if((now.first+1 < p_num && now.second+1 < s_num) && (p[now.first+1] == '?' || p[now.first+1] == s[now.second+1])) {
                q.push(make_pair(now.first+1, now.second+1));
            }
        }
        return false;
    }
};