/* * @lc app=leetcode id=44 lang=cpp * * [44] Wildcard Matching * * https://leetcode.com/problems/wildcard-matching/description/ * * algorithms * Hard (23.27%) * Likes: 1247 * Dislikes: 78 * Total Accepted: 192.8K * Total Submissions: 827.3K * Testcase Example: '"aa"\n"a"' * * Given an input string (s) and a pattern (p), 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). * * Note: * * * s could be empty and contains only lowercase letters a-z. * p could be empty and contains only lowercase letters a-z, and characters * like ? or *. * * * Example 1: * * * Input: * s = "aa" * p = "a" * Output: false * Explanation: "a" does not match the entire string "aa". * * * Example 2: * * * Input: * s = "aa" * p = "*" * Output: true * Explanation: '*' matches any sequence. * * * Example 3: * * * Input: * s = "cb" * p = "?a" * Output: false * Explanation: '?' matches 'c', but the second letter is 'a', which does not * match 'b'. * * * Example 4: * * * Input: * s = "adceb" * p = "*a*b" * Output: true * Explanation: The first '*' matches the empty sequence, while the second '*' * matches the substring "dce". * * * Example 5: * * * Input: * s = "acdcb" * p = "a*c?b" * Output: false * * */classSolution {public:boolisMatch(string s,string p) {constint M =s.size(), N =p.size(); vector<vector<bool>>dp(M +1,vector<bool>(N +1));dp[0][0] =true;for (int j =1; j <= N; ++j) {if (p[j -1] =='*') dp[0][j] =dp[0][j -1]; }for (int i =1; i <= M; ++i) {for (int j =1; j <= N; ++j) {constchar c =p[j -1];if (c =='*') {dp[i][j] =dp[i][j -1] ||dp[i -1][j]; } elseif (s[i -1] == c || c =='?') {dp[i][j] =dp[i -1][j -1]; } } }returndp[M][N]; }};