<p>Given an input string (<code>s</code>) and a pattern (<code>p</code>), implement wildcard pattern matching with support for <code>&#39;?&#39;</code> and <code>&#39;*&#39;</code> where:</p>

<ul>
	<li><code>&#39;?&#39;</code> Matches any single character.</li>
	<li><code>&#39;*&#39;</code> Matches any sequence of characters (including the empty sequence).</li>
</ul>

<p>The matching should cover the <strong>entire</strong> input string (not partial).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aa&quot;, p = &quot;a&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> &quot;a&quot; does not match the entire string &quot;aa&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aa&quot;, p = &quot;*&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong>&nbsp;&#39;*&#39; matches any sequence.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cb&quot;, p = &quot;?a&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong>&nbsp;&#39;?&#39; matches &#39;c&#39;, but the second letter is &#39;a&#39;, which does not match &#39;b&#39;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= s.length, p.length &lt;= 2000</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
	<li><code>p</code> contains only lowercase English letters, <code>&#39;?&#39;</code> or <code>&#39;*&#39;</code>.</li>
</ul>

class Solution {
public:
    bool isMatch(string s, string p) {
        // NO RECURSION: it's not needed as our regex is not very complicated,
        // so let's skip catastrophic backtracking our PATTERN is composed of
        // disjoint GROUPS that must precede each other; the GROUPS are split by
        // the `star (*)` symbol we have as many pointers as we have GROUPS and
        // we slide those pointers from the left to right, making sure the
        // GROUPS don't overlap or overtake each other; the first group might be
        // glued to the start if it is not preceeded by a star (the last group
        // is analogous)

        // Empty pattern edge case:
        if (p.length() == 0)
            return s.length() == 0;

        int POINTERS[2000];
        int GROUP_START[2000];
        int GROUP_LENGTH[2000];

        int groups = 0;

        bool start_group = true;
        bool sticky_first = p[0] != '*';
        bool sticky_last = p[p.length() - 1] != '*';

        int pointer = 0;
        for (int i = 0; i < p.length(); i++) {
            if (p[i] == '*') {
                while (i + 1 < p.length() && p[i + 1] == '*')
                    i++; // skip the annoying repeating stars
                start_group = true;
            } else {
                if (start_group) {
                    POINTERS[groups] = pointer;
                    GROUP_START[groups] = i;
                    GROUP_LENGTH[groups] = 1;
                    start_group = false;
                    groups++;
                } else {
                    GROUP_LENGTH[groups - 1]++;
                }
                pointer++;
            }
        }

        // Return false if the pattern (even excluding stars)
        // is too long:
        if (pointer > s.length())
            return false;

        // LOGS
        // for (int i = 0; i < groups; i++) {
        //     std::cout << "Group " << i << ":\n";
        //     for (int j = GROUP_START[i]; j < GROUP_START[i] +
        //     GROUP_LENGTH[i];
        //          j++) {
        //         std::cout << p[j];
        //     }
        //     std::cout << "\n";
        // }
        // std::cout << "\n";

        // Return true if the pattern consists of only stars (as we already know
        // it's not empty):
        if (groups == 0)
            return true;

        // If the last group must match the end of the string (no star at the
        // end), move it to the end of the string:
        if (sticky_last) {
            while (POINTERS[groups - 1] + GROUP_LENGTH[groups - 1] !=
                   s.length())
                POINTERS[groups - 1]++;
        }

        while (true) {
            // LOGS
            // int k = 0;
            // int i = 0;
            // while (i < s.length()) {
            //     if (k < groups && i == POINTERS[k]) {
            //         for (int j = GROUP_START[k];
            //              j < GROUP_START[k] + GROUP_LENGTH[k]; j++) {
            //             std::cout << p[j];
            //             i++;
            //         }
            //         k++;
            //     } else {
            //         std::cout << "_";
            //         i++;
            //     }
            // }
            // std::cout << "\n";
            // for (int i = 0; i < s.length(); i++) {
            //     std::cout << s[i];
            // }
            // std::cout << "\n";
            // std::cout << "\n";

            // Check if groups are already matched or get the first unmatched
            // group from the right:
            if (sticky_first) {
                if (POINTERS[0] != 0)
                    return false;
            }
            bool all_matched = true;
            int group_to_move;
            for (int i = groups - 1; i >= 0; i--) {
                for (int j = 0; j < GROUP_LENGTH[i]; j++) {
                    if (p[GROUP_START[i] + j] == '?')
                        continue;
                    if (p[GROUP_START[i] + j] != s[POINTERS[i] + j]) {
                        all_matched = false;
                        group_to_move = i;
                        break;
                    }
                }
                if (!all_matched)
                    break;
            }
            if (all_matched) {
                return true;
            }

            // If we can move the group_to_move, we move it, otherwise we move
            // the first movable group from its right:
            if (group_to_move == groups - 1) {
                if (POINTERS[groups - 1] + GROUP_LENGTH[groups - 1] <
                    s.length()) {
                    POINTERS[groups - 1]++;
                    continue;
                }
            } else {
                if (POINTERS[group_to_move] + GROUP_LENGTH[group_to_move] <
                    POINTERS[group_to_move + 1]) {
                    POINTERS[group_to_move]++;
                    continue;
                }
            }

            for (group_to_move = group_to_move + 1; group_to_move < groups;
                 group_to_move++) {
                if (group_to_move == groups - 1) {
                    if (POINTERS[groups - 1] + GROUP_LENGTH[groups - 1] <
                        s.length()) {
                        POINTERS[groups - 1]++;
                        break;
                    }
                } else if (POINTERS[group_to_move] +
                               GROUP_LENGTH[group_to_move] <
                           POINTERS[group_to_move + 1]) {
                    POINTERS[group_to_move]++;
                    break;
                }
            }
            // Return false if we can't move any group:
            if (group_to_move == groups) {
                return false;
            }
        }
    }
};
10529