根据模式串构造最小数字

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

给你下标从?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'?。

思路分析

首先我们还是要先来理解一下题意，题目会给出一串只包含I和D两种字符的字符串，其中'I'?表示?上升，即如果?pattern[i] == 'I'?，那么?num[i] < num[i + 1]?，'D'?表示?下降，即如果?pattern[i] == 'D'?，那么?num[i] > num[i + 1]?。我们需要构造一个下标从?0?开始长度为?n + 1?的字符串，字符串应该满足题目给出参数的升降规则，而且是满足上述条件字典序?最小?的字符串 num。

暴力搜索

我们来看一下数据范围：1 <= pattern.length <= 8，最多只有9位数，所以我们其实是可以通过暴力搜索来得出答案的：

回溯模拟，遍历到位置i时，我们查看在1-9中找到一个数，满足pattern[i]，继续往下拼接。当遍历到结尾，我们找到了一个满足条件的数字，维护最小的即可。

var smallestNumber = function(pattern) {
    const used = new Array(10).fill(false);
    let ans;
    function dfs(str, i) {
        if (i >= pattern.length) {
            if (!ans || Number(str) < Number(ans)) {
                ans = str
            }
            return;
        }
        const v = pattern[i];
        const prev = str[i];
        for (let j = 1; j < 10; j++) {
            if (used[j]) continue;
            const bool = v === 'I' ? j > +prev : j < +prev;
            if (bool) {
                used[j] = true;
                dfs(str + j, i + 1)
                used[j] = false;
            }
        }
    }
    for (let i = 1; i < 10; i++) {
        used[i] = true;
        dfs(`${i}`, 0)
        used[i] = false;
    }
    return ans;
};

贪心，找规律

那么还有没有其他的方法呢？我们可以从下面几个点入手考虑一下是不是可以使用贪心思想来进行解答。

• 字符串字典序最小

要使整个字符串的字典序最小，我们应该尽可能的将数值小的数字放在前面。

• 当前下标位置最大取值

当前位置的最大取值与给出pattern相对位置的字符有关，如果当前位置是I（上升的），我们可以直接取当前没用过的数字的最小值即可，如果是D（下降的），那我们则需要预留出给其下降的空间，如DD,说明它需要连续下降两次，所以我们需要预留出一个数字。也就是说我们当前位置的取值会受到pattern相对位置后面连续D字符的数量的影响，所以我们只需要统计一下连续D的后缀个数即可，具体代码如下：

/**
 * @param {string} pattern
 * @return {string}
 */
 var smallestNumber = function(pattern) {
     let dd = new Array(pattern.length).fill(0);
     for(let j = pattern.length - 1; j >= 0 ; j--){
         if(j == pattern.length - 1) pattern[j] == 'D' ? dd[j] = 1 : '';
         else{
             if(pattern[j] == 'D') dd[j] = dd[j + 1] + 1;
         }
     }
     let res = '',ind = 0;
     for(let i = 0; i < pattern.length; i++){
         res += res.length + 1 + dd[i] - ind;
         if(dd[i]) ind++;
         else ind = 0;
     }
     if(pattern[pattern.length - 1] == 'I'){
         res += res.length + 1;
     }else{
        res += parseInt(res[res.length - 1]) - 1;
     }
     return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。