标签： 字典树

440.字典序的第K小数字

目标

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

示例 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 <= k <= n <= 10^9

思路

求 1 ~ n 的所有数字按字典序排列后的第 k 个数字。

本来想要参考 386.字典序排数 取第 k 个数字。但是数据范围太大，O(n) 的解法不可行。

题目标签显示的是字典树。想象一棵 10 叉树，根为 0，从第一个孩子 1 开始，如果其子树大小小于剩余的数字个数，直接跳过，访问兄弟节点 2，否则进入下一层，从第一个孩子 10 开始，计算其子树大小，如果小于剩余数字个数，访问兄弟节点 11，否则进入下一层。以此类推。

如何统计子树的大小？可以将当前根节点 l 与兄弟节点 r 一起向下计算，当前层的节点个数 = Math.min(r, n + 1) - 1 - l + 1 即 Math.min(r, n + 1) - l。比如，l == 100, r == 200，计算 100 ~ 200 - 1 的数字个数。注意 r 与 n + 1 取最小值，因为要减 1 所以比较的是 n + 1。

代码


/**
 * @date 2025-06-09 8:44
 */
public class FindKthNumber440 {

    public int findKthNumber(int n, int k) {
        int i = 1;
        k--;
        while (k > 0) {
            int cnt = subTreeNodesCnt(i, n);
            if (cnt <= k) {
                k -= cnt;
                i++;
            } else {
                k--;
                i *= 10;
            }
        }

        return i;
    }

    public int subTreeNodesCnt(int root, int n) {
        int cnt = 0;
        long l = root;
        long r = root + 1;
        while (l <= n) {
            cnt += Math.min(r, n + 1) - l;
            l *= 10;
            r *= 10;
        }
        return cnt;
    }
}

性能

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 <= n <= 5 * 10^4

思路

将 1 ~ n 的所有整数按照字典序排序，要求时间复杂度为 O(n)，空间复杂度为 O(1)。

想象遍历一颗字典树，优先扩展（乘以 10），如果超过 n，则优先将个位数加一（遍历兄弟节点），如果需要进位，则返回父节点（除以10）并将个位数加一（父节点的兄弟节点），接着执行同样的逻辑，扩展，个位数加一，回退。

代码


/**
 * @date 2025-06-08 18:15
 */
public class LexicalOrder386 {

    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0, j = 1; i < n; i++) {
            res.add(j);
            if (j * 10 <= n) {
                j *= 10;
            } else {
                while (j % 10 == 9 || j >= n) {
                    j /= 10;
                }
                j++;
            }
        }
        return res;
    }

}

性能

3291.形成目标字符串需要的最少字符串数I

目标

给你一个字符串数组 words 和一个字符串 target。

如果字符串 x 是 words 中 任意 字符串的 前缀，则认为 x 是一个 有效 字符串。

现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。

示例 1：

输入： words = ["abc","aaaaa","bcdef"], target = "aabcdabc"
输出： 3
解释：
target 字符串可以通过连接以下有效字符串形成：
words[1] 的长度为 2 的前缀，即 "aa"。
words[2] 的长度为 3 的前缀，即 "bcd"。
words[0] 的长度为 3 的前缀，即 "abc"。

示例 2：

输入： words = ["abababab","ab"], target = "ababaababa"
输出： 2
解释：
target 字符串可以通过连接以下有效字符串形成：
words[0] 的长度为 5 的前缀，即 "ababa"。
words[0] 的长度为 5 的前缀，即 "ababa"。

示例 3：

输入： words = ["abcdef"], target = "xyz"
输出： -1

说明：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 5 * 10^3
  • 输入确保 sum(words[i].length) <= 10^5。
  • words[i] 只包含小写英文字母。
  • 1 <= target.length <= 5 * 10^3
  • target 只包含小写英文字母。

思路

有一个字符串数组 words 和目标字符串 target，请你使用最少的字符串前缀组成 target，返回需要的字符串数量，如果无法组成 target 返回 -1。

注意前缀是允许重复使用的，状态个数为 target.length ^ 2，深度为 100，直接使用记忆化搜索会超时。

使用字典树加动态规划可以勉强通过，但是明天的通过不了。

//todo KMP 算法 Z 函数 / 字符串哈希+二分 / AC 自动机

代码


/**
 * @date 2024-12-17 8:59
 */
public class MinValidStrings3291 {

    static public class Trie {
        public boolean isLeaf;
        public Trie[] children;

        public Trie() {
            this.children = new Trie[26];
        }

        public Trie build(String[] dict) {
            Trie root = this;
            for (String word : dict) {
                root = this;
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    int c = chars[i] - 'a';
                    if (root.children[c] == null) {
                        root.children[c] = new Trie();
                    }
                    root = root.children[c];
                }
                root.isLeaf = true;
            }
            return root;
        }

        public int exists(char[] target, int start) {
            int n = target.length;
            int length = 0;
            Trie root = this;
            int c = target[start] - 'a';
            while (root.children[c] != null) {
                root = root.children[c];
                length++;
                start++;
                if (start == n) {
                    break;
                }
                c = target[start] - 'a';
            }
            return length;
        }

    }

    public int minValidStrings_v1(String[] words, String target) {
        Trie root = new Trie();
        root.build(words);
        char[] chars = target.toCharArray();
        int n = chars.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        int length = root.exists(chars, 0);
        for (int i = 0; i < length; i++) {
            dp[i] = 1;
        }

        for (int i = 1; i < n; i++) {
            if (dp[i - 1] == Integer.MAX_VALUE) {
                return -1;
            }
            length = root.exists(chars, i);
            for (int j = i; j < i + length; j++) {
                dp[j] = Math.min(dp[j], dp[i - 1] + 1);
            }
        }

        return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
    }

}

性能

676.实现一个魔法字典

目标

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

实现 MagicDictionary 类：

  • MagicDictionary() 初始化对象
  • void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
  • bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

示例：

输入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

说明：

  • 1 <= dictionary.length <= 100
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写英文字母组成
  • dictionary 中的所有字符串 互不相同
  • 1 <= searchWord.length <= 100
  • searchWord 仅由小写英文字母组成
  • buildDict 仅在 search 之前调用一次
  • 最多调用 100 次 search

思路

实现这样一个数据结构，初始化一个单词列表，查询 给定单词修改一个字母（修改的字母与原字母不能相同）后是否位于字典中。言外之意，要在字典中查找长度相同，但字母有一个不同的单词。

如何判断两个长度 相等 的字符串之间是否只有一个字母不同？直接的想法是逐个字母比较，并记录不同字母的个数，最坏情况下查询的时间复杂度是 O(mn)，m为被查单词的平均长度，n为单词列表长度。

一个更好的想法是构建一颗字典树，这样只需沿着给定单词的路径去查找而无需与字典中单词一一比较，最坏的情况是第一个字母就不同，这样得遍历字典中同级的其它字母下的子树共|Σ|个，时间复杂度降为O(|Σ|m)。最好的情况就是单词的最后一个字母不同，时间复杂度为O(m)。

针对本题的数据范围以及调用次数，暴力解法就足够了，字典树反而体现不出优势。

代码

/**
 * @date 2024-08-12 9:08
 */
public class MagicDictionary676 {

    private String[] dictionary;

    public MagicDictionary676() {

    }

    public void buildDict(String[] dictionary) {
        this.dictionary = dictionary;
    }

    public boolean search(String searchWord) {
        for (String word : dictionary) {
            int length = searchWord.length();
            if (word.length() != length) {
                continue;
            }
            int cnt = 0;
            for (int i = 0; i < length; i++) {
                if (word.charAt(i) != searchWord.charAt(i)) {
                    cnt++;
                }
                if (cnt > 1) {
                    // 提前结束比较，效率有明显提升
                    break;
                }
            }
            if (cnt == 1) {
                return true;
            }
        }
        return false;
    }

}

性能