Clear C++ solution


  • 0
    O

    The main difficulty in this problem is taking care of 0's. They can appear inside the string but not at the beginning or the end of each string.
    Hence in my code, in order to calculate f(n), I recursively calculate f(n-2), f(n-4), ..., and adding 0 padding if necessary.

    My code is following.

    class Solution {
    public:
        vector<string> findStrobogrammatic(int n) {
            if (n == 0) return vector<string>({""});
            if (n == 1) return vector<string>({"0", "1", "8"});
            vector<string> result;
            for (int i=n-2; i>=0; i-=2) {
                for (string s : findStrobogrammatic(i)) {
                    string zeros((n-i-2)/2, '0');
                    result.push_back("1"+zeros+s+zeros+"1");
                    result.push_back("6"+zeros+s+zeros+"9");
                    result.push_back("9"+zeros+s+zeros+"6");
                    result.push_back("8"+zeros+s+zeros+"8");
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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