"""
Runtime: 108 ms, faster than 91.30% of Python3 online submissions for Palindrome Number.
Memory Usage: 13.4 MB, less than 5.03% of Python3 online submissions for Palindrome Number.
"""

class Solution:
    def isPalindrome(self, x: int) -> bool:
        # Hybrid solution
        if x < 0:
            return False
        elif x < 10:
            return True
        elif x % 10 == 0:
            return False

        if x < 1000000000000:
            digits = []

            while x > 0:
                x, rem = divmod(x, 10)
                digits.append(rem)

            n = len(digits)

            for i in range(n // 2):
                if digits[i] != digits[n - 1 - i]:
                    return False
            else:
                return True        
        else:
            from math import log10

            digitCount = int(log10(x)) + 1
            pivotPos = digitCount // 2
            digits = [0 for i in range(pivotPos)]

            for i in range(pivotPos):
                x, rem = divmod(x, 10)
                digits[i] = rem

            if digitCount % 2 == 1:
                # Dropping the middle digit
                x, rem = divmod(x, 10)

            for j in range(pivotPos):
                x, rem = divmod(x, 10)
                if rem != digits[-1-j]:
                    return False
            else:
                return True

"""
Runtime: 72 ms, faster than 98.09% of Python3 online submissions for Wildcard Matching.
Memory Usage: 13.3 MB, less than 66.92% of Python3 online submissions for Wildcard Matching.
"""


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # I intentionally did not use the re library

        matchFound = False


        def subMatch(s, p):
            sLen = len(s)
            pLen = len(p)

            if pLen == sLen:
                for i in range(pLen):
                    if p[i] != '?' and p[i] != s[i]:
                        return False
                else:
                    return True
            else:
                return False


        def tryout(s, fragments):
            nonlocal matchFound

            if s and not fragments:
                matchFound = True
                return
            
            if not s or not fragments:        
                return

            sLen = len(s)

            totalFragLen = sum([len(f) for f in fragments])
            if totalFragLen > sLen:
                return

            leftFrag = fragments[0]
            leftFragLen = len(leftFrag)        
            otherFragLen = totalFragLen - leftFragLen

            for i in range(sLen - otherFragLen):
                if subMatch(s[i:i+leftFragLen], leftFrag):
                    if otherFragLen > 0:
                        tryout(s[i+leftFragLen:], fragments[1:])
                        return
                    else:
                        matchFound = True
                        return


        pLen = len(p)
        sLen = len(s)

        starCount = p.count('*')

        if pLen > 0 and pLen == starCount:
            return True

        if starCount == 0 and not '?' in p:
            return p == s

        if pLen == sLen == 0:
            return True
        elif pLen == 0 or sLen == 0:
            return False

        if starCount == 0:
            return subMatch(s, p)

        if pLen - starCount > sLen:
            return False

        # At this stage, starCount > 0

        starRightEdge = (p[-1] == '*')
        starLeftEdge = (p[0] == '*')

        fragments = [i for i in p.split('*') if i]

        # Trying to match the right side
        if not starRightEdge:
            fragRight = len(fragments[-1])
            if subMatch(s[-fragRight:], fragments[-1]):
                s = s[:-fragRight]     
                fragments = fragments[:-1]
            else:
                return False

        # Trying to match the left side
        if not starLeftEdge:
            fragLeft = len(fragments[0])
            if subMatch(s[:fragLeft], fragments[0]):
                s = s[fragLeft:]     
                fragments = fragments[1:]
            else:
                return False

        if not s and not fragments:
            return True
                
        tryout(s, fragments)

        return matchFound