Strobogrammatic number ii

Array String Recursion

53.5% acceptance

Mar 31, 2026

960

263

Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order. A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_strobogrammatic(n: i32) -> Vec<String> {
    fn helper(n: i32, total: i32) -> Vec<String> {
      if n == 0 {
        return vec!["".to_string()];
      }
      if n == 1 {
        return vec!["0".to_string(), "1".to_string(), "8".to_string()];
      }
      let middles = helper(n - 2, total);
      let mut result = Vec::new();
      for mid in middles {
        let pairs = [('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')];
        for &(a, b) in &pairs {
          if a == '0' && n == total {
            continue;
          }
          result.push(format!("{}{}{}", a, mid, b));
        }
      }
      result
    }
    helper(n, n)
  }
}