2375. Construct Smallest Number From DI String

Обновлено: 2024-03-12
1 мин
[]

Содержание

LeetCode problem 2375

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        def dfs(u):
            nonlocal res
            if res:
                return
            if u == len(pattern) + 1:
                res = ''.join(t)
                return
            for i in range(1, 10):
                if not vis[i]:
                    if u and pattern[u - 1] == 'I' and int(t[-1]) >= i:
                        continue
                    if u and pattern[u - 1] == 'D' and int(t[-1]) <= i:
                        continue
                    vis[i] = True
                    t.append(str(i))
                    dfs(u + 1)
                    vis[i] = False
                    t.pop()

        vis = [False] * 10
        t = []
        res = None
        dfs(0)
        return res