Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // LeetCode URL: https://leetcode.com/problems/lexicographical-numbers/
- import java.util.ArrayList;
- import java.util.List;
- /**
- * Recursive DFS
- *
- * Time Complexity: O(N)
- *
- * Space Complexity: O(log10 N)
- *
- * N = input number n.
- */
- class Solution1 {
- public List<Integer> lexicalOrder(int n) {
- List<Integer> result = new ArrayList<>();
- if (n <= 0) {
- return result;
- }
- for (int i = 1; i <= 9; i++) {
- if (i > n) {
- break;
- }
- dfsHelper(result, i, n);
- }
- return result;
- }
- private void dfsHelper(List<Integer> list, int cur, int n) {
- list.add(cur);
- cur *= 10;
- for (int i = 0; i <= 9; i++) {
- int newCur = cur + i;
- if (newCur > n) {
- return;
- }
- dfsHelper(list, newCur, n);
- }
- }
- }
- /**
- * Iterative
- *
- * Time Complexity: O(N)
- *
- * Space Complexity: O(1)
- *
- * N = input number n.
- */
- class Solution2 {
- public List<Integer> lexicalOrder(int n) {
- List<Integer> result = new ArrayList<>();
- if (n <= 0) {
- return result;
- }
- int cur = 1;
- for (int i = 1; i <= n; i++) {
- result.add(cur);
- if (cur * 10 <= n) {
- cur *= 10;
- } else {
- while (cur % 10 == 9 || cur == n) {
- cur /= 10;
- }
- cur++;
- }
- }
- return result;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement