I have been trying to solve "Wildcard Matching" on leetcode. I know there are more "manual" ways to solve this without using the RE library. But I would like to know if passing the time limit is possible without having to manually create a pattern finder from scratch.
Currently this code times out at test case 1708 (out of 1800 or so). I will put the question, leet code examples and my try in the code block below. The case that exceeds the time limit has been included in the 'inps' list of test cases (it is the last one). Can anyone think of a way to make this faster?
"""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 """ class Solution: def isMatch(self, s, p): """ :type s: str :type p: str :rtype: bool """ import re from itertools import groupby grps = groupby(p) l = [(x, len(list(y))) for x, y in grps] new_p = '' for c, cnt in l: if c == '*': new_p = ''.join([new_p, '.*']) elif c == '?': new_p = ''.join([new_p, '.{', str(cnt), '}']) else: new_p = ''.join([new_p, c * cnt]) p = '^' + new_p + '$' MY_RE = re.compile(p) return True if MY_RE.match(s) else False # string, patter, expected inps = [ ("aa", "a", False), ("aa", "*", True), ("cb", "?a", False), ("adceb", "*a*b", True), ("acdcb", "a*c?b", False), ("abcdef", "", False), ("abcdef", "*", True), ("abcdef", "??????", True), ("abcdef", "a?c?e?", True), ("abcdef", "a?c?e?", True), ("abcdef", "********************", True), ("abcdef", "*****abcdef*****", True), ("abcdef", "?abcdef?", False), ("", "", True), ("", "*", True), ("", "*****", True), ("", "?", False), ("a", "*********?********", True), ("a", "?", True), ("abc", "?*?", True), ( "aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba", "*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*", True, ), ( "abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb", "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb", False, ), ] sol = Solution() for s, p, exp in inps: #print(f"Doing string[{s}] with pattern[{p}] and asserting...") assert sol.isMatch(s, p) == exp 
