386. Lexicographical Numbers
Tags:
Medium
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu liệt kê tất cả các số từ 1 → n theo thứ tự từ điển (lexicographical order), tức là sắp xếp như chuỗi: 1, 10, 11,..2,20,21,…9,90,91,…
Phân tích và ý tưởng
Approach - Iterative
Solution - Iterative
1function lexicalOrder(n: number): number[] {
2 const ans: number[] = [];
3 let v = 1;
4 for(let i = 0; i < n; i++) {
5 ans.push(v);
6 if(v * 10 <= n) {
7 v *= 10;
8 } else {
9 while (v % 10 === 9 || v === n) {
10 v = Math.floor(v / 10);
11 }
12 ++v
13 }
14 }
15 return ans;
16};Solution - DFS
1function lexicalOrder(n: number): number[] {
2 const ans: number[] = [];
3 function dfs(curr: number) {
4 if(curr > n) return;
5 ans.push(curr);
6 for(let i = 0; i <= 9; i++) {
7 const next = curr * 10 + 1;
8 if(next > n) break;
9 dfS(next)
10 }
11 }
12
13 for(let i = 1; i <= 9; i++) {
14 dfs(i);
15 }
16
17 return ans;
18};