[数据结构与算法]LeetCode 6150. 根据模式串构造最小数字 DFS全排列+贪心

题目描述

给你下标从 0 开始、长度为 n 的字符串 pattern ，它包含两种字符，‘I’ 表示 上升 ，‘D’ 表示 下降 。

你需要构造一个下标从 0 开始长度为 n + 1 的字符串，且它要满足以下条件：

num 包含数字 ‘1’ 到 ‘9’ ，其中每个数字 至多 使用一次。
如果 pattern[i] == ‘I’ ，那么 num[i] < num[i + 1] 。
如果 pattern[i] == ‘D’ ，那么 num[i] > num[i + 1] 。
请你返回满足上述条件字典序 最小 的字符串 num。

示例 1：

输入：pattern = “IIIDIDDD”
输出：“123549876”
解释：
下标 0 ，1 ，2 和 4 处，我们需要使 num[i] < num[i+1] 。
下标 3 ，5 ，6 和 7 处，我们需要使 num[i] > num[i+1] 。
一些可能的 num 的值为 “245639871” ，“135749862” 和 “123849765” 。
“123549876” 是满足条件最小的数字。
注意，“123414321” 不是可行解因为数字 ‘1’ 使用次数超过 1 次。
示例 2：

输入：pattern = “DDD”
输出：“4321”
解释：
一些可能的 num 的值为 “9876” ，“7321” 和 “8742” 。
“4321” 是满足条件最小的数字。

提示：

1 <= pattern.length <= 8
pattern 只包含字符 ‘I’ 和 ‘D’ 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-smallest-number-from-di-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题意分析

给定一个模式串，返回按照模式串组成的字典序最小的字符串
关键词：“按模式” “字典序最小”
一眼贪心法

贪心

模式分为递增I和递减D
根据贪心的思路：

每当递增时，为满足字典序最小，要从最小的数字开始递增
每当递减时，为满足字典序最小，要从最小的最大值开始递减（递减序列的最后一个元素应当是递增序列的最后一个元素+1）

则可以维护一个本身为递增的字符串，每当遇到递减时，就从该值向后计数递减序列的长度cnt，然后将字符串的该序列部分反转即可

作者：endless_developy
链接：https://leetcode.cn/problems/construct-smallest-number-from-di-string/solution/c-by-endless_developy-hu0b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# from string import digits # “0123...9”
# 因为leetcode帮忙引入了，就不用再引入了
class Solution:
    def smallestNumber(self, pattern: str) -> str:
        n = len(pattern)
        ans = list(digits[1 : n + 2])
        i = 0  # 维护当前走到哪里
        while i < n:
            if pattern[i] == 'I':
                i += 1
                continue
            i0 = i # D的起点
            i += 1
            while i < n and pattern[i] == 'D':
                i += 1
            # 翻转
            ans[i0 : i + 1] = ans[i0: i + 1][::-1]
        
        # 这个''.join太秀了
        return ''.join(ans)

class Solution {
public:
    string smallestNumber(string pattern) {
        int limit = pattern.size() + 1;
        // 弄一个本事为递增的字符串
        string a;
        for (int i = 1; i <= limit; i ++ ) a += (char)(i + '0');

        int p = 0;
        while (p < limit - 1) {
            if (pattern[p] == 'I') ++ p;
            else {
                int cnt = 0, t = p;
                while (p < limit - 1 && pattern[p] == 'D') cnt ++, p ++;
                // 将递增序列反转
                reverse(a.begin() + t, a.begin() + t + cnt + 1);
            }
        }

        return a;
    }
};

暴力

class Solution {
private:
    bool check(const string &pattern, const string &p) {
        for (int i = 0; i < pattern.size(); i++) {
            if (pattern[i] == 'I' && p[i] > p[i + 1])
                return false;

            if (pattern[i] == 'D' && p[i] < p[i + 1])
                return false;
        }

        return true;
    }

public:
    string smallestNumber(string pattern) {
        const int n = pattern.size();

        string p;
        for (int i = 0; i <= n; i++)
            p += i + 1 + '0';

        string ans;

        do {
            if (!check(pattern, p))
                continue;
            // 因为这个next_permutation函数本来就是按照字典序返回的
            // 所以不需要再维护一个最小值了，找到之后直接break就行了
            // if (ans.empty() || ans > p)
                ans = p;
                break;

        } while (next_permutation(p.begin(), p.end()));

        return ans;
    }
};

// 作者：wzc1995
// 链接：https://www.acwing.com/file_system/file/content/whole/index/content/6380152/
// 来源：AcWing
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

拓扑排序+优先队列

https://leetcode.cn/problems/construct-smallest-number-from-di-string/solution/by-wangzhizhi-n03o/

参考

https://www.acwing.com/file_system/file/content/whole/index/content/6380152/