Leetcode 248: Strobogrammatic number III

July 1, 2018

Introduction

It is a hard level algorithm called Strobogrammatic  Number III. I like to get into the hard work and spend 30 minutes to work on the algorithm.

I like to read the problem statement and think about using first 20 minutes. Now it is 3:12 PM.

Now it is 3:22 PM. I took some time off. Let me write down something here to help me out, I need to focus on the problem solving.

Problem statement:

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

First 20 minutes of thinking 

I think that there are 3 numbers for first the position, 6, 9 or 8, once it is determined, then last digit is also determined. Brute force solution should just try all options and see if it is in the range.

Time complexity is related to how many possible numbers. We only need to return how many numbers, we do not need to return a list of those numbers.

So we should simplify the algorithm by just check every 10 number, 100 numbers, or 1000, etc. how many possible numbers in total. It should speed up calculation.

Solutions

Now it is 3:49 PM. Let me search the solution. It is not easy to figure out the hard level algorithm. I should read II algorithm first, here is the blog.

Now it is 5:04 PM. I just copied the idea from the blog: http://www.cnblogs.com/grandyang/p/5203228.html

这道题是之前那两道 Strobogrammatic Number II 和 Strobogrammatic Number 的拓展，又增加了难度，让我们找到给定范围内的对称数的个数，我们当然不能一个一个的判断是不是对称数，我们也不能直接每个长度调用第二道中的方法，保存所有的对称数，然后再统计个数，这样OJ会提示内存超过允许的范围，所以我们的解法是基于第二道的基础上，不保存所有的结果，而是在递归中直接计数，根据之前的分析，需要初始化 n = 0 和 n = 1 的情况，然后在其基础上进行递归，递归的长度 len从 low到 high之间遍历，然后我们看当前单词长度有没有达到 len，如果达到了，我们首先要去掉开头是0的多位数，然后去掉长度和 low相同但小于 low的数，和长度和 high相同但大于 high的数，然后结果自增 1，然后分别给当前单词左右加上那五对对称数，继续递归调用.