Skip to content

Latest commit

 

History

History
292 lines (246 loc) · 7.31 KB

File metadata and controls

292 lines (246 loc) · 7.31 KB
comments difficulty edit_url rating source tags
true
中等
1641
第 306 场周赛 Q3
贪心
字符串
回溯

English Version

题目描述

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

解法

方法一:DFS

定义 $dfs(u)$,其中 $u$ 表示当前答案字符串的长度。从 $u=0$ 开始搜索,直至找到第一个符合条件的字符串。

时间复杂度 $O(n!)$,空间复杂度 $O(n)$。其中 $n$ 表示字符串 $pattern$ 的长度。

Python3

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 ans

Java

class 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;
            }
        }
    }
}

C++

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;
            }
        }
    }
};

Go

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
}

TypeScript

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('');
}