Depth First Search Algorithm to Find the Strobogrammatic Number of Given Length

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n.

Example:
Input: n = 2
Output: [“11″,”69″,”88″,”96”]

Hints:
Try to use recursion and notice that it should recurse with n – 2 instead of n – 1.

Depth First Search Algorithm

A valid Strobogrammatic contains only digits from [0, 1, 6, 8, 9]. We can use Depth First Search Algorithm to bruteforce all possibilities with given size N, then use the routine from here to check if it is a valid Strobogrammatic number. Special case is zero which is only valid when length is 1.

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        dfs(n, "");
        return res;
    }
    
private:
    vector res;
    
    void dfs(int n, string cur) {
        if (n == 0) {
            if (isStrobogrammatic(cur)) {
                if ((cur.size() > 1) && (cur[0] == '0')) return;
                res.push_back(cur);
            }
            return;
        }
        for (const auto &s: {"0", "1", "6", "8", "9"}) {
            dfs(n - 1, cur + s);
        }
    }
    
    bool isStrobogrammatic(string num) {
        int len = num.size();
        for (int i = 0; i < len; ++ i) {
            switch (num[i] - 48) {
                case 2:
                case 3:
                case 4:
                case 5:
                case 7: return false;
                case 6: if ('9' != num[len - 1 - i]) return false; break;
                case 9: if ('6' != num[len - 1 - i]) return false; break;
                case 1:
                case 8: 
                case 0: if (num[i] != num[len - 1 - i]) return false; break;
            }
        }
        return true;
    }    
};

This is not ideal, as we have to go through O(N) to check if the final string is valid Strobogrammatic, the runtime complexity is O(N*5^N) – which is exponetial.

Improved Depth First Search Algorithm

We can get rid of the Strobogrammatic checking by only placing the valid digits. First we define a [left, right] range where the next valid digits are. If we place a digit at [left] position we have to place its corresponding digit at [right]. This will reduce the complexity to O(5^N/2)

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        dfs(0, n - 1, string(n, ' '));
        return res;
    }
    
private:
    vector<string> res;
    
    void dfs(int left, int right, string cur) {
        if (left > right) {
            if ((cur.size() > 1) && (cur[0] == '0')) return;
            res.push_back(cur);
            return;
        }
        for (const auto &s: {'0', '1', '8'}) {
            cur[left] = s;
            cur[right] = s;
            dfs(left + 1, right - 1, cur);
        }
        if (left < right) {
            for (const auto &s: {'6', '9'}) {
                cur[left] = s;
                cur[right] = s == '6' ? '9' : '6';
                dfs(left + 1, right - 1, cur);
            }        
        }
    }   
};

Both algorithms have O(N) space complexity due to implicit stack usage from Recursion.

–EOF (The Ultimate Computing & Technology Blog) —