Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 484 with 12 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 484 # by problem number
lcpy gen -s find_permutation # by problem name
perm of n integers of all the integers in the range [1, n] can be represented as a string s of length n - 1 where:
s[i] == 'I' if perm[i] < perm[i + 1], ands[i] == 'D' if perm[i] > perm[i + 1].s, reconstruct the lexicographically smallest permutation perm and return it.
Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.
Input: s = "DI"
Output: [2,1,3]
Explanation: Both [2,1,3] and [3,1,2] can be represented as "DI", but since we want to find the smallest lexicographical permutation, you should return [2,1,3].
1 <= s.length <= 10^5s[i] is either 'I' or 'D'.class Solution:
# Time: O(n)
# Space: O(1) extra (output excluded)
def find_permutation(self, s: str) -> list[int]:
n = len(s) + 1
perm = list(range(1, n + 1))
i = 0
while i < len(s):
if s[i] == "D":
j = i
while j < len(s) and s[j] == "D":
j += 1
perm[i : j + 1] = perm[i : j + 1][::-1]
i = j
else:
i += 1
return perm
| Time | Space |
|---|---|
| O(n) | O(1) extra (output excluded) |