C++ DFS easy solution


  • 0

    from inner to outside

    class Solution {
    public:
        vector<char> cand1 = {'1', '0', '8', '6' ,'9'},
                     cand2 = {'1', '0', '8', '9', '6'};
        void helper(vector<string>& res, int len, string s) {
            if (s.size() == len) {
                res.push_back(s);
                return;
            }
            
            for (int i = 0; i < 5; i++) {
                if (len & 1 && s.empty()) {
                    if (i <= 2)
                        helper(res, len, string(1,cand1[i]));
                } else {
                    if (s.size() == len - 2 && i == 1) // do not generate 0 start string like 01810
                        continue;
                    helper(res, len, cand1[i] + s + cand2[i]);
                }
            }
            
        }
        vector<string> findStrobogrammatic(int n) {
            vector<string> res;
            helper(res, n, "");
            return res;
        }
    };
    

    from outside to inner

    class Solution {
    public:
        vector<char> cand = {'0', '1', '8', '6', '9'};
        
        vector<string> findStrobogrammatic(int n) {
            
            vector<string> res;
            dfs(res, "", n);
            // for (auto i : res)
            //     cout << i << endl;
            return res;
        }
        
        char opp(char c) {
            switch (c) {
                case '0':
                case '1':
                case '8':
                    return c;
                case '6':
                    return '9';
                case '9':
                    return '6';
                default:
                    break;
            }
            return c;
        }
        void dfs(vector<string>& res, string s, int n) {
            if (s.size() == n / 2) {
                for (int i = s.size() - 1; i >= 0; i--) {
                    s.push_back(opp(s[i]));
                }
                if (s.size() < n) {
                    for (int i = 0; i < 3; i++) {
                        res.push_back(s.substr(0, n / 2) + cand[i] + s.substr(n / 2));
                    }
                } else
                    res.push_back(s);
                return;
            }
            
            for (int i = 0; i < cand.size(); i++) {
                if (s.empty() && i == 0)
                    continue;
                dfs(res, s + cand[i], n);
            }
            
        }
    };
    

Log in to reply
 

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