题解 | #通配符匹配#

递归+备忘录优化

import java.util.HashMap;
import java.util.Objects;

public class Solution {
    public static void main(String[] args) {
        System.out.println(new Solution().isMatch("abc", "*?c"));
    }

    private HashMap<Tuple, Boolean> memo = new HashMap<>();

    public boolean isMatch(String str, String pattern) {
        return dp(str, pattern, 0, 0);
    }

    private boolean dp(String str, String pattern, int i, int j) {
        Tuple t = new Tuple(i, j);
        if (memo.containsKey(t)) return memo.get(t);
        if (j == pattern.length()) return i == str.length();
        if (i == str.length()) {
            for (int k = j; k < pattern.length(); k++)
                if (pattern.charAt(k) != '*') return false;
            return true;
        }
        boolean res = false;
        boolean single = (i < str.length()) && (str.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '?');    // 处理单个字符以及'.'

        if (pattern.charAt(j) == '*') {
            res = dp(str, pattern, i, j + 1) || dp(str, pattern, i + 1, j);
        } else {
            res = single && dp(str, pattern, i + 1, j + 1);
        }
        memo.put(new Tuple(i, j), res);
        return res;
    }

    class Tuple {
        int first, second;

        public Tuple(int first, int second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Tuple tuple = (Tuple) o;
            return first == tuple.first &&
                    second == tuple.second;
        }

        @Override
        public int hashCode() {
            return Objects.hash(first, second);
        }
    }
}