Strobogrammatic number iii

Array String Recursion

42.7% acceptance

Mar 31, 2026

307

193

Given two strings low and high that represent two integers low and high where low <= high, return the number of strobogrammatic numbers in the range [low, high]. 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 strobogrammatic_in_range(low: String, high: String) -> i32 {
    let lo_len = low.len();
    let hi_len = high.len();
    let mut count = 0;
    for n in lo_len..=hi_len {
      let nums = Self::generate(n as i32, n as i32);
      for num in nums {
        if num.len() == lo_len && num < low {
          continue;
        }
        if num.len() == hi_len && num > high {
          continue;
        }
        count += 1;
      }
    }
    count
  }

  fn generate(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 = Self::generate(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
  }
}