Depth First Search Algorithm to Find the Strobogrammatic Number

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

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

推荐阅读：
刷鞋作文400字　 闲游伏羲公园作文500字　 包装纸上的讲究作文1000字　 写人作文完美的她作文　 放花炮的作文　 流浪　 六一亲子游作文800字　 观《雪景》有感　 清晨的雾的作文　 题目生命　
评论列表
添加评论