跳转至

LeetCode: 484. 寻找排列

1、题目描述

现在给定一个只由字符 'D''I' 组成的 秘密签名。'D' 表示两个数字间的递减关系,'I' 表示两个数字间的递增关系。并且 秘密签名 是由一个特定的整数数组生成的,该数组唯一地包含 1n 中所有不同的数字(秘密签名的长度加 1 等于 n)。例如,秘密签名 "DI" 可以由数组 [2,1,3][3,1,2] 生成,但是不能由数组 [3,2,4][2,1,3,4] 生成,因为它们都不是合法的能代表 "DI" 秘密签名 的特定串。

现在你的任务是找到具有最小字典序的 [1, 2, ... n] 的排列,使其能代表输入的 秘密签名。

示例 1:

输入: "I"
输出: [1,2]
解释: [1,2] 是唯一合法的可以生成秘密签名 "I" 的特定串,数字 1 和 2 构成递增关系。

示例 2:

输入: "DI"
输出: [2,1,3]
解释: [2,1,3] 和 [3,1,2] 可以生成秘密签名 "DI",
但是由于我们要找字典序最小的排列,因此你需要输出 [2,1,3]。

注:

  • 输出字符串只会包含字符 'D''I'
  • 输入字符串的长度是一个正整数且不会超过 10,000

2、解题思路

  • 贪心法
  • 首先顺序排列,保证最小字典序
  • 然后遇到连续的D,就进行反转
from itertools import groupby


class Solution:
    def findPermutation(self, s: str) -> List[int]:
        pos = 0
        ans = list(range(1, len(s) + 2))
        for k, vals in groupby(s):
            cur_length = len(list(vals))
            if k == "D":
                ans[pos:pos + cur_length + 1] = reversed(ans[pos:pos + cur_length + 1])
            pos += cur_length
        return ans