247. Strobogrammatic Number II

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"]

Rust Solution

struct Solution;
use std::collections::HashMap;

impl Solution {
    fn find_strobogrammatic(n: i32) -> Vec<String> {
        let mut res = vec![];
        let hm: HashMap<char, char> =
            vec![('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')]
                .into_iter()
                .collect();
        let n = n as usize;
        let mut cur: Vec<char> = vec![];
        Self::dfs(0, &mut cur, &mut res, &hm, n);
        res
    }

    fn dfs(
        i: usize,
        cur: &mut Vec<char>,
        all: &mut Vec<String>,
        hm: &HashMap<char, char>,
        n: usize,
    ) {
        if i == n {
            all.push(cur.iter().collect());
        } else {
            for (&k, &v) in hm {
                if n != 1 && i == 0 && k == '0' {
                    continue;
                }
                let j = n - 1 - i;
                if j < i && cur[j] != v {
                    continue;
                }
                if j == i && k != v {
                    continue;
                }
                cur.push(k);
                Self::dfs(i + 1, cur, all, hm, n);
                cur.pop();
            }
        }
    }
}

#[test]
fn test() {
    let n = 1;
    let mut res = vec_string!["0", "1", "8"];
    let mut ans = Solution::find_strobogrammatic(n);
    res.sort();
    ans.sort();
    assert_eq!(ans, res);
    let n = 2;
    let mut res = vec_string!["11", "69", "88", "96"];
    let mut ans = Solution::find_strobogrammatic(n);
    res.sort();
    ans.sort();
    assert_eq!(ans, res);
}

Having problems with this solution? Click here to submit an issue on github.