0903. Valid Permutations for DI Sequence

题目信息

题号:

0903

难度:

Hard

主题:

排列、相邻大小关系、计数

原题:

LeetCode 0903

重点:

长度为 n 的模式约束 0 至 n 的排列;I 和 D 分别规定相邻元素严格递增或严格递减

题目重述

给定只包含字符 I 和 D 的字符串 s,令其长度为 n。考虑由整数 0, 1, ..., n 各使用恰好一次组成的所有长度为 n + 1 的排列 perm。

对于每个下标 i:若 s[i] == 'I',必须满足 perm[i] < perm[i + 1];若 s[i] == 'D',必须满足 perm[i] > perm[i + 1]。请返回满足全部相邻关系的排列数量,并对 10^9 + 7 取模。

1 <= s.length <= 200。

自建示例

先升后降:

输入:s = "ID"
输出:2
解释:需要排列 0、1、2,并满足 perm[0] < perm[1] > perm[2]。合法排列为 [0,2,1] 和 [1,2,0]。

模式长度达到最小值:

输入:s = "I"
输出:1
解释:只需排列 0、1,并满足前者小于后者;唯一合法排列是 [0,1]。