| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
1641 |
第 306 场周赛 Q3 |
|
给你下标从 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 <= 8pattern只包含字符'I'和'D'。
定义
时间复杂度
class Solution:
def smallestNumber(self, pattern: str) -> str:
def dfs(u):
nonlocal ans
if ans:
return
if u == len(pattern) + 1:
ans = ''.join(t)
return
for i in range(1, 10):
if not vis[i]:
if u and pattern[u - 1] == 'I' and int(t[-1]) >= i:
continue
if u and pattern[u - 1] == 'D' and int(t[-1]) <= i:
continue
vis[i] = True
t.append(str(i))
dfs(u + 1)
vis[i] = False
t.pop()
vis = [False] * 10
t = []
ans = None
dfs(0)
return ansclass Solution {
private boolean[] vis = new boolean[10];
private StringBuilder t = new StringBuilder();
private String p;
private String ans;
public String smallestNumber(String pattern) {
p = pattern;
dfs(0);
return ans;
}
private void dfs(int u) {
if (ans != null) {
return;
}
if (u == p.length() + 1) {
ans = t.toString();
return;
}
for (int i = 1; i < 10; ++i) {
if (!vis[i]) {
if (u > 0 && p.charAt(u - 1) == 'I' && t.charAt(u - 1) - '0' >= i) {
continue;
}
if (u > 0 && p.charAt(u - 1) == 'D' && t.charAt(u - 1) - '0' <= i) {
continue;
}
vis[i] = true;
t.append(i);
dfs(u + 1);
t.deleteCharAt(t.length() - 1);
vis[i] = false;
}
}
}
}class Solution {
public:
string ans = "";
string pattern;
vector<bool> vis;
string t = "";
string smallestNumber(string pattern) {
this->pattern = pattern;
vis.assign(10, false);
dfs(0);
return ans;
}
void dfs(int u) {
if (ans != "") return;
if (u == pattern.size() + 1) {
ans = t;
return;
}
for (int i = 1; i < 10; ++i) {
if (!vis[i]) {
if (u && pattern[u - 1] == 'I' && t.back() - '0' >= i) continue;
if (u && pattern[u - 1] == 'D' && t.back() - '0' <= i) continue;
vis[i] = true;
t += to_string(i);
dfs(u + 1);
t.pop_back();
vis[i] = false;
}
}
}
};func smallestNumber(pattern string) string {
vis := make([]bool, 10)
t := []byte{}
ans := ""
var dfs func(u int)
dfs = func(u int) {
if ans != "" {
return
}
if u == len(pattern)+1 {
ans = string(t)
return
}
for i := 1; i < 10; i++ {
if !vis[i] {
if u > 0 && pattern[u-1] == 'I' && int(t[len(t)-1]-'0') >= i {
continue
}
if u > 0 && pattern[u-1] == 'D' && int(t[len(t)-1]-'0') <= i {
continue
}
vis[i] = true
t = append(t, byte('0'+i))
dfs(u + 1)
vis[i] = false
t = t[:len(t)-1]
}
}
}
dfs(0)
return ans
}function smallestNumber(pattern: string): string {
const n = pattern.length;
const res = new Array(n + 1).fill('');
const vis = new Array(n + 1).fill(false);
const dfs = (i: number, num: number) => {
if (i === n) {
return;
}
if (vis[num]) {
vis[num] = false;
if (pattern[i] === 'I') {
dfs(i - 1, num - 1);
} else {
dfs(i - 1, num + 1);
}
return;
}
vis[num] = true;
res[i] = num;
if (pattern[i] === 'I') {
for (let j = res[i] + 1; j <= n + 1; j++) {
if (!vis[j]) {
dfs(i + 1, j);
return;
}
}
vis[num] = false;
dfs(i, num - 1);
} else {
for (let j = res[i] - 1; j > 0; j--) {
if (!vis[j]) {
dfs(i + 1, j);
return;
}
}
vis[num] = false;
dfs(i, num + 1);
}
};
dfs(0, 1);
for (let i = 1; i <= n + 1; i++) {
if (!vis[i]) {
res[n] = i;
break;
}
}
return res.join('');
}