2375. Construct Smallest Number From DI String

Problem

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.

https://leetcode.com/problems/construct-smallest-number-from-di-string/

Example 1:

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

Example 2:

Input: pattern = "DDD"
Output: "4321"
Explanation:
Some possible values of num are "9876", "7321", and "8742".
It can be proven that "4321" is the smallest possible num that meets the conditions.

Constraints:

1 <= pattern.length <= 8
pattern consists of only the letters 'I' and 'D'.

Test Cases

1 2	class Solution: def smallestNumber(self, pattern: str) -> str:

solution_test.py

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('pattern, expected', [
    ("IIIDIDDD", "123549876"),
    ("DDD", "4321"),

    ("IDID", "13254"),
    ("IIDDID", "1254376"),
    ("IDDIID", "1432576"),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2()])
def test_solution(sol, pattern, expected):
    assert sol.smallestNumber(pattern) == expected

Thoughts

用类似 1718. Construct the Lexicographically Largest Valid Sequence 的回溯法。

首先如果 pattern 的长度为 n，那么结果数字想要最小的话应该用数字 1 到 n + 1（否则假设数字 k 没使用，那么把 k + 1 换成 k 仍然符合 pattern，继续把 k + 2 换成 k + 1……，最终还是用到 1 到 n + 1）。

结果数字一共有 n + 1 个位置，从最左边开始，对于每个位置从小到大遍历所有未被占用的数字，然后递归地处理下一个位置。最左边的位置可以从 1 试到 n + 1；其他位置则要先检查 pattern 中对应的前一位的值，如果是 "I" 则下界为前一个数字加一，如果是 "D" 则上界为前一个数字减一。

时间复杂度 O(n!)，空间复杂度 O(n)。

Code

solution.py

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        n = len(pattern)
        m = n + 1
        used = [False] * (m + 1)
        result = [0] * m

        def backtrack(i: int) -> bool:
            if i == m:
                return True

            lo, hi = 1, m
            if i > 0:
                if pattern[i - 1] == 'I':
                    lo = result[i - 1] + 1
                else:
                    hi = result[i - 1] - 1

            for d in range(lo, hi + 1):
                if not used[d]:
                    used[d] = True
                    result[i] = d
                    if backtrack(i + 1):
                        return True
                    used[d] = False

            return False

        backtrack(0)
        return ''.join(map(str, result))

Faster

前边提到长度为 n 的 pattern，结果数字应该只用到数字 1 到 n + 1。

如果 pattern 中没有 "D"，显然结果数字应该为 1 到 n + 1 的升序排列，即 "123...n{n+1}"。

如果只有最后 k 位是 "D"，那么结果数字的前 n - k 位依然用从 1 开始的递增数字，而最后 k + 1 位把剩余的数字降序排列即可，即 "123...{n-k}{n+1}n{n-1}...{n-k+1}"。

如果有若干组 "D"，只需要对每一组的 k 个 "D" 所对应的 k + 1 个位置（加上最后一个 "D" 右边一个位置）按降序排列原本这些位置的数字即可。

TODO: 更优雅的解释。

时间复杂度 O(n)，空间复杂度 O(n)。

solution2.py

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        n = len(pattern)
        result = list(range(1, n + 2)) # [1, 2, 3, ..., n+1]
        i = 0
        while i < n:
            if pattern[i] == 'D':
                j = i
                while j < n and pattern[j] == 'D':
                    j += 1
                result[i:j+1] = range(j+1, i, -1)
                i = j
            i += 1

        return ''.join(map(str, result))