2375. Construct Smallest Number From DI String

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/construct-smallest-number-from-di-string
• topics: Backtracking

Description

You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.

A 0-indexed string num of length n + 1 is created using the following conditions:

• num consists of the digits '1' to '9', where each digit is used at most once.
• If pattern[i] == 'I', then num[i] < num[i + 1].
• If pattern[i] == 'D', then num[i] > num[i + 1].

Return the lexicographically smallest possible string num that meets the conditions.

Idea

• Backtrack

Code

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        ans = None
        def backtrack(prev, used):
            nonlocal ans
            if ans:
                return
            i = len(prev)
            if i == len(pattern) + 1:
                ans = "".join(str(c) for c in prev)
                return
            for k in range(1, 10):
                if used[k-1]:
                    continue
                if i > 0 and (pattern[i-1] == "I" and k < prev[-1] or pattern[i-1] == "D" and k > prev[-1]):
                    continue
                prev.append(k)
                used[k-1] = True  
                backtrack(prev, used)
                prev.pop()
                used[k-1] = False
 
        backtrack([], [False] * 9)
        return ans