641. Smallest From Pattern
A pattern string of length m made of the letters I (increase) and D (decrease) describes how consecutive digits of a secret code compare. Build the code d[0] d[1] ... d[m] of m + 1 digits from 1 to 9, using every digit at most once, so that for every position i: if pattern[i] is I then d[i] < d[i + 1], and if it is D then d[i] > d[i + 1].
Return the numerically smallest such code as a string. A valid code always exists for the allowed patterns.
Example 1
- Input:
- pattern = "ID"
- Output:
- "132"
- Explanation:
The smallest triple that rises then falls is
132: 1 < 3 > 2.
Example 2
- Input:
- pattern = "DDI"
- Output:
- "3214"
- Explanation:
Three falls would be needed to start with 1, so the first digits must be 3, 2, 1... then rise:
3214.
Example 3
- Input:
- pattern = "IDDID"
- Output:
- "143265"
- Explanation:
The rises and falls give
143265: 1 < 4 > 3 > 2 < 6 > 5.
Constraints
- 1 ≤
pattern.length≤ 8 patternconsists only of the lettersIandD.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(m)
- Space
- O(m)