Trie DFS and O(n) iterative


  • 0
    S

    Build a Trie

    class Solution {
    public:
        class TrieNode {
        public:
            char d;
            vector<TrieNode*> nextTable;
            bool output;
            TrieNode(char c) :d(c) {
                nextTable.resize(10, 0);
                output = false;
            }
        };
        
        void insertNum(TrieNode *head, string &s) {
            TrieNode *cur = head;
            for (int i = 0; i < s.size(); i++) {
                int id = s[i] - '0';
                if (!cur->nextTable[id]) {
                    cur->nextTable[id] = new TrieNode(s[i]);
                }
                cur = cur->nextTable[id];
            }
            cur->output = true;
        }
        
        void dfs(TrieNode *cur, int val, vector<int> &collector) {
            if (!cur) return;
            int curVal = val * 10 + cur->d - '0';
            if (cur->output) {
                collector.push_back(curVal);
            }
            
            for (int i = 0; i < cur->nextTable.size(); i++) {
                dfs(cur->nextTable[i], curVal, collector);
            }
        }
    
        vector<int> lexicalOrder(int n) {
            TrieNode *head = new TrieNode('0');
            for (int i = 1; i <= n; i++) {
                string s = to_string(i);
                insertNum(head, s);
            }
            vector<int> ret;
            dfs(head, 0, ret);
            return ret;
        }
    };
    

    O(n) get Next value

    class Solution {
    public:
        vector<int> lexicalOrder(int n) {
            vector<int> ret(n, 0);
            int cur = 1;
            int i = 0;
            while (i < n) {
                ret[i++] = cur;
                
                //getNext
                if (cur * 10 <= n) {
                    cur *= 10;
                } else {
                    if (cur == n) {
                        cur /= 10;
                    }
                    cur++;
                    while ((cur % 10) == 0) {
                        cur /= 10;
                    }
                }
            }
            return ret;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.