DFS + BFS


  • 0
    N

    DFS

    vector<string> letterCombinations(string digits) {
        vector<string> res;
        string tmp_list;
        unordered_map<char, string> table;
        table['2'] = "abc";
        table['3'] = "def";
        table['4'] = "ghi";
        table['5'] = "jkl";
        table['6'] = "mno";
        table['7'] = "pqrs";
        table['8'] = "tuv";
        table['9'] = "wxyz";
        backtracking(0, digits, tmp_list, res, table);
        return res;
    }
    
    void backtracking(int pos, string digits, string tmp_list, vector<string>& res, unordered_map<char, string>& table) {
        if (pos >= digits.length()) {
            if (tmp_list.length()) {
                res.push_back(tmp_list);
            }
            return;
        }
        
        if (table.find(digits[pos]) == table.end()) {
            backtracking(pos + 1, digits, tmp_list, res, table);
        } else {
            string charset = table[digits[pos]];
            for (int i = 0; i < charset.length(); i++) {
                tmp_list += charset[i];
                backtracking(pos + 1, digits, tmp_list, res, table);
                tmp_list = tmp_list.substr(0, tmp_list.length() - 1);
            }
       }   
    }
    

    Fix1: I should not use unordered_map as a table. I failed to notice that phone digit is natural index...

    The dfs application is obvious and implementation is straightforward. However BFS is the interesting part

    2 BFS

    The code is borrowed from
    https://discuss.leetcode.com/topic/8465/my-java-solution-with-fifo-queue

    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        queue <string> q;
        if(digits.empty()) { return {}; }
        vector<string> mapping {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        q.push("");
        // control depth of tree
        for (int i = 0; i < digits.size(); i++){
            int x = digits[i] - '0';
            //control each level of the tree
            while (q.front().size() == i) {
                string t = q.front();
                q.pop();
                for (char s : mapping[x])
                    q.push(t + s);
            }
        }
        
       while (!q.empty()) { 
           ans.push_back(q.front());
           q.pop();
       }
       return ans;
    }
    

    Fix1: how to differentiate between different levels

    I was able to see this is a level-matter BFS, which means after we discovered nodes of the same level, we got some work for further purpose (here is to update the digit index for building neighbors ). This reminds me of "Level Traverse of Binary Tree", we count the number of node in each tree, so that we can output nodes level by level. I was trying the similar way , the code works but looks bad. The code above is a clever way to solve the level-matter problem by using
    " while (q.front().size() == i)" very good observation.


Log in to reply
 

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