用字典树处理字典序的问题

  |  

摘要: 几个字符串上的字典序问题,用字典树可以解决

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


在文章 字典序法枚举排列 中,我们了解到对于一个排列来说,可以用字典序来定义这些排列的大小,进一步可以用字典序枚举全排列。

字符串也可以根据字典序的方式比较大小或者排序,字典树是解决这类问题有力的数据结构,本文我们看几个相关题目。


$1 386. 字典序排数

给你一个整数 n ,按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

示例 1:
输入:n = 13
输出:[1,10,11,12,13,2,3,4,5,6,7,8,9]

示例 2:
输入:n = 2
输出:[1,2]

提示:

1
1 <= n <= 5e4

算法1: 字典树前序遍历

字符集是 0123456789,将所有数字插入到字典树。

按字典序输出所有数字,即对字典树前序遍历,将所有插入的数字输出,实现时与 N 叉树的前序遍历没有区别。

代码 (C++)

Trie 的代码模板的基础上,traverse()dfs() 是本题中对字典树进行遍历的逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
struct TrieNode {
const int ALPHABETS = 10;
vector<TrieNode*> children;
bool terminal;
TrieNode()
{
terminal = false;
children = vector<TrieNode*>(ALPHABETS, nullptr);
}
~TrieNode(){}
};

class Trie {
public:
Trie() {
root = new TrieNode();
}

~Trie() {
delete root;
root = nullptr;
}

void insert(int num) {
TrieNode *iter = root;
vector<int> digits;
while(num)
{
int c = num % 10;
num /= 10;
digits.push_back(c);
}
reverse(digits.begin(), digits.end());
for(int c: digits)
{
if(!(iter -> children[c]))
(iter -> children)[c] = new TrieNode();
iter = (iter -> children)[c];
}
iter -> terminal = true;
}

bool search(int num) {
const TrieNode* iter = find(num);
return iter && iter -> terminal;
}

bool startsWith(int prefix) {
return find(prefix) != nullptr;
}

vector<int> traverse()
{
int item = 0;
vector<int> result;
dfs(root, item, result);
return result;
}

private:
TrieNode *root;

void delete_sub_tree(TrieNode *node)
{
for(TrieNode *child: node -> children)
if(child)
delete_sub_tree(child);
delete node;
node = nullptr;
}

void dfs(TrieNode* node, int item, vector<int>& result)
{
if(node -> terminal)
{
result.push_back(item);
}
item *= 10;
for(int i = 0; i <= 9; ++i)
{
TrieNode *son = node -> children[i];
if(son)
{
item += i;
dfs(son, item, result);
item -= i;
}
}
}

const TrieNode* find(int prefix) const
{
const TrieNode* iter = root;
vector<int> digits;
while(prefix)
{
int c = prefix % 10;
prefix /= 10;
digits.push_back(c);
}
reverse(digits.begin(), digits.end());
for(int c: digits)
{
iter = (iter -> children)[c];
if(iter == nullptr) break;
}
return iter;
}
};

class Solution {
public:
vector<int> lexicalOrder(int n) {
Trie trie;
for(int i = 1; i <= n; ++i)
trie.insert(i);
vector<int> result = trie.traverse();
return result;
}
};

算法2:DFS

这里的数字结合是 1~N。

字典树可以处理更复杂的数字集合,这里因为数字集合很简单,用字典树有点奢侈了。只需要把字典树前序遍历的部分拿出来,写成一个单独的 DFS 即可。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
vector<int> lexicalOrder(int n) {
int item = 0;
vector<int> result;
dfs(item, result, n);
return result;
}

void dfs(int item, vector<int>& result, const int n)
{
if(item > n)
return;
if(item > 0)
result.push_back(item);
item *= 10;
for(int i = 0; i <= 9; ++i)
{
if(item == 0 && i == 0)
continue;
item += i;
dfs(item, result, n);
item -= i;
}
}
};

$2 440. 字典序的第K小数字

给定整数 n 和 k,返回 [1, n] 中字典序第 k 小的数字。

提示:

1
1 <= k <= n <= 1e9

示例 1:
输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9],所以第二小的数字是 10。

示例 2:
输入: n = 1, k = 1
输出: 1

算法1:字典树

可以套用字典树前序遍历的做法。

代码 (C++)

但是因为 n 很大,直接遍历会超时。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int findKthNumber(int n, int k) {
Trie trie;
for(int i = 1; i <= n; ++i)
trie.insert(i);
vector<int> result = trie.traverse();
return result[k - 1];
}
};

算法2:DFS + 剪枝

在一棵假想的字典树树上进行 DFS,k 表示要找到此后的第 k 个元素,起始下标是 0。

获取以 prefix 开头的数字个数,包括他本身:

  • 如果数字个数大于k,则在假想的字典树下移,在 prefix * 10 下的子树进行查找
  • 如果数字个数小于等于k,右移,在 prefix + 1 下的子树进行查找

在求以 prefix 开头的数字个数的时候,难点在于有一个 <= n 的限制。

1
2
3
根节点 [prefix, prefix + 1)
第一层 [prefix * 10, (prefix + 1) * 10 )
第二层 [prefix * 100, min(n + 1, (prefix + 1) * 100))

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
int findKthNumber(int n, int k) {
int prefix = 1;
k--; // k 记录要找的数字在prefix后的第几个
while(k > 0)
{
int cnt = getCnt(n, prefix); // 当前 prefix 下有多少个元素; 包含 prefix
if (cnt <= k)
{
// 向右
k -= cnt;
++prefix;
}
else
{
// 向下
--k;
prefix *= 10;
}
}
return prefix;
}

private:
using ll = long long;

int getCnt(ll n, ll prefix){
ll cnt = 0;
for(ll first = prefix, second = prefix + 1; first <= n; first *= 10, second *= 10)
{
cnt += min(n + 1, second) - first;
}
return cnt;
}
};

$3 1643. 第 K 条最小指令

Bob 站在单元格 (0, 0) ,想要前往目的地 destination :(row, column) 。他只能向 右 或向 下 走。你可以为 Bob 提供导航 指令 来帮助他到达目的地 destination 。

指令 用字符串表示,其中每个字符:

  • ‘H’ ,意味着水平向右移动
  • ‘V’ ,意味着竖直向下移动

能够为 Bob 导航到目的地 destination 的指令可以有多种,例如,如果目的地 destination 是 (2, 3),”HHHVV” 和 “HVHVH” 都是有效 指令 。

然而,Bob 很挑剔。因为他的幸运数字是 k,他想要遵循 按字典序排列后的第 k 条最小指令 的导航前往目的地 destination 。k 的编号 从 1 开始 。

给你一个整数数组 destination 和一个整数 k ,请你返回可以为 Bob 提供前往目的地 destination 导航的 按字典序排列后的第 k 条最小指令 。

提示:

1
2
3
destination.length == 2
1 <= row, column <= 15
1 <= k <= nCr(row + column, row),其中 nCr(a, b) 表示组合数,即从 a 个物品中选 b 个物品的不同方案数。

示例 1:
输入:destination = [2,3], k = 1
输出:”HHHVV”
解释:能前往 (2, 3) 的所有导航指令 按字典序排列后 如下所示:
[“HHHVV”, “HHVHV”, “HHVVH”, “HVHHV”, “HVHVH”, “HVVHH”, “VHHHV”, “VHHVH”, “VHVHH”, “VVHHH”].

示例 2:
输入:destination = [2,3], k = 2
输出:”HHVHV”

示例 3:
输入:destination = [2,3], k = 3
输出:”HHVVH”

算法:字典树

在假想的 Trie 上从高位向低位走。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
string kthSmallestPath(vector<int>& destination, int k) {
int n = destination[0], m = destination[1];
// n + 1 个 V,m + 1 个 H
int kV = n, kH = m;
c = vector<vector<int>>(kV + kH + 1, vector<int>(kH + 1, 0));
preprocess(kV + kH, kH);
string result;
int remain = kV + kH;
int kh = kH;
for(int i = 0; i < kV + kH; ++i)
{
// 当前放 H 型成的前缀对应的串数目
if(remain == kh)
{
result += string(remain, 'H');
break;
}
if(kh == 0)
{
result += string(remain, 'V');
break;
}
int cnt_H = c[remain - 1][kh - 1];
if(cnt_H >= k)
{
result += 'H';
--kh;
}
else
{
result += 'V';
k -= cnt_H;
}
--remain;
}
return result;
}

private:
vector<vector<int>> c;

void preprocess(int n, int m)
{
for(int i = 0; i <= n; ++i)
c[i][0] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= min(i, m); ++j)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]);
}
};

$4 1415. 长度为 n 的开心字符串中字典序第 k 小的字符串

一个 「开心字符串」定义为:

  • 仅包含小写字母 [‘a’, ‘b’, ‘c’].
  • 对所有在 1 到 s.length - 1 之间的 i ,满足 s[i] != s[i + 1] (字符串的下标从 1 开始)。

比方说,字符串 “abc”,”ac”,”b” 和 “abcbabcbcb” 都是开心字符串,但是 “aa”,”baa” 和 “ababbc” 都不是开心字符串。

给你两个整数 n 和 k ,你需要将长度为 n 的所有开心字符串按字典序排序。

请你返回排序后的第 k 个开心字符串,如果长度为 n 的开心字符串少于 k 个,那么请你返回 空字符串 。

提示:

1
2
1 <= n <= 10
1 <= k <= 100

示例 1:
输入:n = 1, k = 3
输出:”c”
解释:列表 [“a”, “b”, “c”] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 “c” 。

示例 2:
输入:n = 1, k = 4
输出:””
解释:长度为 1 的开心字符串只有 3 个。

示例 3:
输入:n = 3, k = 9
输出:”cab”
解释:长度为 3 的开心字符串总共有 12 个 [“aba”, “abc”, “aca”, “acb”, “bab”, “bac”, “bca”, “bcb”, “cab”, “cac”, “cba”, “cbc”] 。第 9 个字符串为 “cab”

示例 4:
输入:n = 2, k = 7
输出:””

示例 5:
输入:n = 10, k = 100
输出:”abacbabacb”

算法:字典树

在假想的 Trie 上从高位向低位走。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
string getHappyString(int n, int k) {
string result;
if(3 * pow(2, n - 1) < k)
return "";
int len = n;
while(len > 0)
{
// c := 限定上一个字符后,长为 len - 1 的开心串个数
int c = pow(2, len - 1);
int num = 1;
for(char ch = 'a'; ch <= 'c'; ++ch)
{
if(!result.empty() && ch == result.back())
continue;
if(num * c >= k)
{
result += ch;
break;
}
++num;
}
k -= (num - 1) * c;
--len;
}
return result;
}
};

Share