Lexicographical Numbers

MediumDepth-First SearchTrie

Solution

Solution1: `Sort`

export function lexicalOrder(n: number): number[] {
  return Array.from({ length: n }, (_, i) => i + 1).sort();
}

Complexity

Time: O(NlogN)
Space: O(1)
- sort로 인하여 N만큼의 추가 공간이 필요하지만 고려하지 않음

Solution2: `DFS`

export function lexicalOrder(n: number): number[] {
  const answer: number[] = [];
  function dfs(num: number): void {
    if (n < num) {
      return;
    }
    answer.push(num);
    for (let digit = 0; digit < 10; digit++) {
      dfs(10 * num + digit);
    }
  }
  for (let i = 1; i < 10; i++) {
    dfs(i);
  }
  return answer;
}

Complexity

Time: O(N)
Space: O(1)

Lexicographical Numbers

https://leetcode.com/problems/lexicographical-numbers