_2375. Construct Smallest Number From DI String.md

2375. Construct Smallest Number From DI String

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : February 18, 2025

Last updated : February 18, 2025

---

Related Topics : String, Backtracking, Stack, Greedy

Acceptance Rate : 85.85 %

---

Solutions

• m2375.py

Python

m2375.py

class Solution:
    # i defaults to -1 since the first value doesn't "satisfy" part of the pattern
    def dfs(self, pot_vals: List[int], pattern: str, i: int = -1, output: List[str] = None) -> bool | List[str] :
        if output is None :
            output = []
        if not pot_vals or i >= len(pattern):
            return output

        # Checks smallest values first for leftmost indices
        for j in range(len(pot_vals) - 1, -1, -1) :
            if not output or \
               (pot_vals[j] < output[-1] and pattern[i] == 'D') or \
               (pot_vals[j] > output[-1] and pattern[i] == 'I') :
                output.append(pot_vals.pop(j))
                nxt = self.dfs(pot_vals, pattern, i + 1, output)
                if nxt :
                    return nxt
                pot_vals.insert(j, output.pop())

        return False

    def smallestNumber(self, pattern: str) -> str:
        return ''.join(map(str, self.dfs(list(reversed(range(1, len(pattern) + 2))), pattern)))