Depth First Search Algorithm to Find the Strobogrammatic Number

  • 时间：2020-10-11 15:17:18
  • 分类：网络文摘
  • 阅读：133 次

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. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        dfs(n, "");
        return res;
    }
    
private:
    vector<string> 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;
    }    
};
</string>
class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        dfs(n, "");
        return res;
    }
    
private:
    vector<string> 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;
    }    
};
</string>

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*5N) – 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(5N/2) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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);
            }        
        }
    }   
};
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) —

推荐阅读：
Remember Your Blog Is A Reflection Of You　 Learn About Blog Content Planning　 Adding PHPUnit Tests for Discord Cryptocurrency Bot Regarding th　 Algorithm to Multiply Two Big Integers (String)　 Use jQuery Migrate Helper Plugin to Fix the Classic Editor Error　 How to Fix CloudFlare Error 1101 (Worker threw exception)?　 Python Function to Convert Excel Sheet Column Titles to Numbers　 Algorithm to Find the Kth Missing Positive Number in Array　 How to Partition a String into Palindromes using DFS Algorithm?　 How to Get Blockchain Version of Steem RPC Node using Javascript　
评论列表
添加评论