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

字数统计: 2.4k字 | 阅读时长: 11分

2020-09-09

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

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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() 是本题中对字典树进行遍历的逻辑。

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++)

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 很大，直接遍历会超时。

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++)

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++)

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++)

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

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法字符串

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

$1 386. 字典序排数

算法1: 字典树前序遍历

代码 (C++)

算法2：DFS

代码 (C++)

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

算法1：字典树

代码 (C++)

算法2：DFS + 剪枝

代码 (C++)

$3 1643. 第 K 条最小指令

算法：字典树

代码 (C++)

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

算法：字典树

代码 (C++)