LC 3348. 最小可整除数位乘积 II

https://leetcode.cn/problems/smallest-divisible-digit-product-ii/description/

这题看了题解，主要的障碍在于怎么应对如果需要更长的字符串。如果是相同长度的字符串的话，那么使用数位DP就行。这里的数位DP其实缓存的不是最终结果，缓存的是哪些不可行的结果。因为我们是按照顺序来搜索的，所以如果一旦找到正确的结果就可以返回。

为了应对“需要更长的字符串”这种情况，可以针对num进行对齐。假设t包含x个因子的话，那么长度x的字符串肯定是满足条件的。假设t可以分解为3个2和2个5，那么'22255' 是肯定满足条件的。我们按照这个长度对num进行补齐就行。对于补齐的部分可以先看看'0'是否满足，如果不满足的话在尝试之后的结果。

class Solution:
    def smallestNumber(self, num: str, t: int) -> str:
        cnt = 0
        t2 = t
        for p in (2, 3, 5, 7):
            while t2 % p == 0:
                t2 = t2 // p
                cnt += 1
        if t2 != 1:
            return "-1"

        pad = max(cnt - len(num), 0) + 1
        num = '0' * pad + num

        def gcd(a, b):
            while b != 0:
                a, b = b, a % b
            return a

        ans = [0] * len(num)

        import functools
        @functools.lru_cache(None)
        def dfs(i, t, cap):
            if i == len(num):
                # print(ans, t)
                return t == 1

            if i < pad and not cap:
                if dfs(i + 1, t, cap):
                    return True

            d = int(num[i])
            low = d if not cap else 0
            for x in range(max(low, 1), 10):
                ans[i] = x
                if dfs(i + 1, t // gcd(t, x), cap or (x > d)):
                    return True
            return False

        dfs(0, t, False)
        dfs.cache_clear()
        ans = ''.join([str(x) for x in ans])
        # print(ans)
        return ans.lstrip('0')