## Tuesday, September 6, 2016

### LeetCode OJ - Lexicographical Numbers

Problem:

Analysis:

Suppose we are trying to do the lexicographical order for 213, here is how it should look like

1
10
100
101
...
109
11
110
111
...
199
2
20
200
201
...
213
22
23
...

The goal is to spot the pattern.

Solution:

By using an example, we can see some interesting rules:

Rule 1: Whenever possible, add 1 zero (e.g. 1 -> 10, 10->100)
Rule 2: If not possible to add zero (because it is too large) add 1. (e.g. 100->101)
Rule 3: If rule 2 result in any trailing zero, remove all of them. (e.g. 199 -> 200 -> 20 -> 2)
Rule 4: If reaching 'n', just fake it as if it reaches zero and apply rule 3. (213 -> 220 -> 22)

Applying this 4 rules, we can derive the order as needed. This approach requires only constant space!

Code:

#include "stdafx.h"

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

#include "LEET_LEXICOGRAPHICAL_NUMBERS.h"
#include <stack>
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_LEXICOGRAPHICAL_NUMBERS
{
class Solution
{
public:
vector<int> lexicalOrder(int n)
{
vector<int> result;
result.resize(n);
int level = 0;
int c = n;
while (c > 0)
{
level++;
c = c / 10;
}

int current = 1;
int currentLevel = 1;

for (int i = 0; i < n; i++)
{
result[i] = current;
if ((currentLevel < level) && (current * 10 <= n))
{
// We always try to increase the number of digit
current = current * 10;
currentLevel++;
}
else
{
if (current == n)
{
// Take all the digits but the last one, increase by 1, and then add a zero
// e.g. 134 -> 13 -> 14 -> 140
current = ((current / 10) + 1) * 10;
}
else
{
current++;
}
while (current % 10 == 0)
{
// Whenever possible, remove trailing zero
currentLevel--;
current /= 10;
}
}
}
return result;
}
};
};

using namespace _LEET_LEXICOGRAPHICAL_NUMBERS;

int LEET_LEXICOGRAPHICAL_NUMBERS()
{
Solution solution;
vector<int> r = solution.lexicalOrder(234);
for (int i = 0; i < r.size(); i++)
{
cout << r[i] << endl;
}
return 0;
}