<p>You are given a <strong>0-indexed</strong> string <code>pattern</code> of length <code>n</code> consisting of the characters <code>&#39;I&#39;</code> meaning <strong>increasing</strong> and <code>&#39;D&#39;</code> meaning <strong>decreasing</strong>.</p>

<p>A <strong>0-indexed</strong> string <code>num</code> of length <code>n + 1</code> is created using the following conditions:</p>

<ul>
	<li><code>num</code> consists of the digits <code>&#39;1&#39;</code> to <code>&#39;9&#39;</code>, where each digit is used <strong>at most</strong> once.</li>
	<li>If <code>pattern[i] == &#39;I&#39;</code>, then <code>num[i] &lt; num[i + 1]</code>.</li>
	<li>If <code>pattern[i] == &#39;D&#39;</code>, then <code>num[i] &gt; num[i + 1]</code>.</li>
</ul>

<p>Return <em>the lexicographically <strong>smallest</strong> possible string </em><code>num</code><em> that meets the conditions.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> pattern = &quot;IIIDIDDD&quot;
<strong>Output:</strong> &quot;123549876&quot;
<strong>Explanation:
</strong>At indices 0, 1, 2, and 4 we must have that num[i] &lt; num[i+1].
At indices 3, 5, 6, and 7 we must have that num[i] &gt; num[i+1].
Some possible values of num are &quot;245639871&quot;, &quot;135749862&quot;, and &quot;123849765&quot;.
It can be proven that &quot;123549876&quot; is the smallest possible num that meets the conditions.
Note that &quot;123414321&quot; is not possible because the digit &#39;1&#39; is used more than once.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> pattern = &quot;DDD&quot;
<strong>Output:</strong> &quot;4321&quot;
<strong>Explanation:</strong>
Some possible values of num are &quot;9876&quot;, &quot;7321&quot;, and &quot;8742&quot;.
It can be proven that &quot;4321&quot; is the smallest possible num that meets the conditions.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= pattern.length &lt;= 8</code></li>
	<li><code>pattern</code> consists of only the letters <code>&#39;I&#39;</code> and <code>&#39;D&#39;</code>.</li>
</ul>

class Solution:
    def __init__(self):
        self.possible_nums = [1,2,3,4,5,6,7,8,9]
        self.pattern = ''
        self.lowest = 1
        self.highest = 9
        self.num = 999_999_999
    def smallestNumber(self, pattern: str) -> str:
        self.num = 999_999_999
        self.highest = len(pattern) + 1
        self.pattern = pattern
        for i in range(self.lowest, self.highest + 1):
            self.get_all_possible_nums(cur_nums=[i], cur_ltr=self.pattern[0])
        return f'{self.num}'

    def get_all_possible_nums(self, cur_nums, cur_num=None, cur_ltr=''):
        if cur_num is None:
            cur_num = cur_nums[0]
        if cur_ltr == '':
            num = self.list_to_num(cur_nums)
            self.num = min(self.num, num)
            return
        # Setting the inclusive range we will need to go over to find the next
        # number.
        if cur_ltr == 'D':
            start = self.lowest
            end = cur_num-1
        else:
            start = cur_num+1
            end = self.highest

        for i in range(start, end+1):
            if i in cur_nums:
                continue
            is_valid_lower = i < cur_num and cur_ltr == 'D'
            is_valid_higher = i > cur_num and cur_ltr == 'I'
            if is_valid_lower or is_valid_higher:
                cur_nums.append(i)
                nxt_ltr = ''
                if len(cur_nums) <= len(self.pattern):
                    nxt_ltr = self.pattern[len(cur_nums)-1]
                outcome = self.get_all_possible_nums(cur_nums, cur_num=i, cur_ltr=nxt_ltr)
                if outcome:
                    num = self.list_to_num(cur_nums)
                    self.num = min(self.num, num)
                cur_nums.pop()
        return []
    def list_to_num(self, l):
        s = ''.join([str(i) for i in l])
        if len(s) == 0:
            return 999_999_999
        return int(s)
135