What is the approach to solving Valid Permutations for DI Sequence?

The problem is solved using dynamic programming with state transitions, ensuring that the conditions set by the DI sequence are met.

How can I optimize the solution for Valid Permutations for DI Sequence?

Focus on reducing unnecessary recalculations by properly utilizing dynamic programming and ensuring each transition step is calculated only once.

What is the time complexity of solving Valid Permutations for DI Sequence?

The time complexity is O(n^2), where n is the length of the sequence, due to the need to evaluate all possible transitions.

What is the modulo value used in Valid Permutations for DI Sequence?

The modulo value used in this problem is 10^9 + 7 to handle large numbers and prevent overflow.

What are some common mistakes when solving Valid Permutations for DI Sequence?

Common mistakes include mishandling the modulo operation, incorrect state transitions, and overcomplicating the dynamic programming setup.

#903

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

DI 序列的有效排列

给定一个长度为 n 的字符串 s ，其中 s[i] 是: “D” 意味着减少，或者 “I” 意味着增加有效排列是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ，使得对所有的 i ：如果 s[i] == 'D' ，那么 perm[i] > perm[i+1] ，以及； …

字符串动态规划前缀和

题目描述

给定一个长度为 n 的字符串 s ，其中 s[i] 是:

“D” 意味着减少，或者
“I” 意味着增加

有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ，使得对所有的 i：

如果 s[i] == 'D'，那么 perm[i] > perm[i+1]，以及；
如果 s[i] == 'I'，那么 perm[i] < perm[i+1]。

返回 有效排列 perm的数量 。因为答案可能很大，所以请返回你的答案对 10⁹ + 7 取余。

示例 1：

输入：s = "DID"
输出：5
解释：
(0, 1, 2, 3) 的五个有效排列是：
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)

示例 2:

输入: s = "D"
输出: 1

提示:

n == s.length
1 <= n <= 200
s[i] 不是 'I' 就是 'D'

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示字符串的前 $i$ 个字符中，以数字 $j$ 结尾的满足题目要求的排列的数量。初始时 $f[0][0]=1$ ，其余 $f[0][j]=0$ 。答案为 $\sum_{j=0}^n f[n][j]$ 。

考虑 $f[i][j]$ ，其中 $j \in [0, i]$ 。

如果第 $i$ 个字符 $s[i-1]$ 是 'D'，那么 $f[i][j]$ 可以从 $f[i-1][k]$ 转移而来，其中 $k \in [j+1, i]$ ，而由于 $k-1$ 最大只能为 $i-1$ ，我们将 $k$ 向左移动一位，那么 $k \in [j, i-1]$ ，因此有 $f[i][j] = \sum_{k=j}^{i-1} f[i-1][k]$ 。

如果第 $i$ 个字符 $s[i-1]$ 是 'I'，那么 $f[i][j]$ 可以从 $f[i-1][k]$ 转移而来，其中 $k \in [0, j-1]$ ，因此有 $f[i][j] = \sum_{k=0}^{j-1} f[i-1][k]$ 。

最终的答案即为 $\sum_{j=0}^n f[n][j]$ 。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是字符串的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def numPermsDISequence(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        f = [[0] * (n + 1) for _ in range(n + 1)]
        f[0][0] = 1
        for i, c in enumerate(s, 1):
            if c == "D":
                for j in range(i + 1):
                    for k in range(j, i):
                        f[i][j] = (f[i][j] + f[i - 1][k]) % mod
            else:
                for j in range(i + 1):
                    for k in range(j):
                        f[i][j] = (f[i][j] + f[i - 1][k]) % mod
        return sum(f[n][j] for j in range(n + 1)) % mod

我们可以用前缀和优化时间复杂度，使得时间复杂度降低到 $O(n^2)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def numPermsDISequence(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        f = [[0] * (n + 1) for _ in range(n + 1)]
        f[0][0] = 1
        for i, c in enumerate(s, 1):
            pre = 0
            if c == "D":
                for j in range(i, -1, -1):
                    pre = (pre + f[i - 1][j]) % mod
                    f[i][j] = pre
            else:
                for j in range(i + 1):
                    f[i][j] = pre
                    pre = (pre + f[i - 1][j]) % mod
        return sum(f[n][j] for j in range(n + 1)) % mod

另外，我们也可以用滚动数组优化空间复杂度，使得空间复杂度降低到 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def numPermsDISequence(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        f = [1] + [0] * n
        for i, c in enumerate(s, 1):
            pre = 0
            g = [0] * (n + 1)
            if c == "D":
                for j in range(i, -1, -1):
                    pre = (pre + f[j]) % mod
                    g[j] = pre
            else:
                for j in range(i + 1):
                    g[j] = pre
                    pre = (pre + f[j]) % mod
            f = g
        return sum(f) % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands dynamic programming concepts and is able to apply them to a string-based problem.
question_mark
The candidate can model state transitions based on string patterns like 'I' and 'D'.
question_mark
The candidate is capable of handling large numbers with modulo arithmetic.

warning

常见陷阱

外企场景

error
Failing to properly handle the modulo operation, leading to overflow errors.
error
Not accounting for all valid transitions when switching between 'I' and 'D' sequences.
error
Overcomplicating the solution without recognizing that dynamic programming and state transitions can simplify the problem.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to work with permutations of a different set of integers, such as from 0 to n-1.
arrow_right_alt
Introduce additional constraints, like allowing both 'I' and 'D' at the same index in the sequence.
arrow_right_alt
Consider a similar problem where the goal is to find the number of valid permutations that satisfy multiple sequences of 'I' and 'D'.

help

常见问题

外企场景

继续练习

#1871 跳跃游戏 VII #902 最大为 N 的数字组合 #926 将字符串翻转到单调递增