LeetCode刷题——字典序排数#386#Medium

字典序排数的思路探讨与源码
    字典序排数的题目如下图，该题属于搜索类和树类型的题目，主要考察对于搜索方法的使用和树结构的理解。本文的题目作者想到2种方法，分别是递归方法和前缀树方法，其中递归方法使用Java进行编写，而前缀树方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。

    本人认为该题目可以使用递归方法的思路进行解决，首先定义一个整数列表，然后进行遍历循环，在循环内部进行递归搜索。在搜索函数内部，判断传入数字是否超过上限值，如果超过就返回结果，否则就将数字加入列表，然后继续遍历循环，在循环内部用数字乘以10加上下标进行搜索，直到最终搜索结束并返回结果。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟
class Solution {
    List res = new ArrayList<>();
    public List lexicalOrder(int n) {
        for (int ir = 1; ir <= 9; ir++){
            dfsSearch(ir,n);
        }
        return res;
    }
    void dfsSearch(int ind, int limitNum) {
        if (ind > limitNum) return ;
        res.add(ind);
        for (int jr = 0; jr <= 9; jr++){
            dfsSearch(ind * 10 + jr, limitNum);
        }
    }
}

    显然，我们的递归方法的效果还不错，还可以使用前缀树的方法解决。首先初始化参数，然后开始嵌套循环，在循环内部执行搜索函数，在搜索函数的内部进行迭代器的遍历操作，直到最终遍历结束并返回结果。所以按照这个思路就可以解决，下面是Python代码：

#喷火龙与水箭龟
class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        def dfsSearch(x):
            yield x
            for jrs in range(x * 10, min(n + 1, (x + 1) * 10)):
                yield from dfsSearch(jrs)

        return [kr for ir in range(1, min(n + 1, 10)) for kr in dfsSearch(ir)]

    从结果来说Java版本递归方法的效率不错，而Python版本的前缀树方法的速度比较一般，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。