# Daily Archives: January 27, 2016

## Strobogrammatic Number II, III

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.

For example,

Given n = 2, return [“11″,”69″,”88″,”96”].

Solution. The basic idea is to iterate from inside to outside. If n is even, we just start from “”. If n is odd, the initial inside should start from”0″, “1”, “8”.
When it reach the outside(length is n), we should ignore those whose first element is “0”.

In leetcode discussion, most popular way is similar to below:

```public static final char[][] chs = {{'6', '9'}, {'9', '6'}, {'1', '1'}, {'8', '8'}, {'0', '0'}};

public static List<String> findStrobogrammatic(int n) {
return findHelper(n, n);
}

public static ArrayList<String> findHelper(int num, int n) {
if (num == 1) {
return new ArrayList<String>(Arrays.asList("0", "1", "8"));  // handle the middle one
}
else if (num <= 0) {
return new ArrayList<String>(Arrays.asList(""));  // handle the middle one
}
List<String> list = findHelper(num - 2, n);
int to = (num == n ? 3 : 4);    // if is last outside, 0 shouldn't be considered
ArrayList<String> newList = new ArrayList<String>();
for (String str : list) {
for (int i = 0; i <= to; i++)
}
list = null;
return newList;
}

```

It is a very awesome way of concise code. But to me, first it is not easy to think this method. Second, it is not a common way.

However, I feel more comfortable with code like below. It is more standard. It is a bit longer. But I can finish it within 10 minutes. You can find my other recursion solution all coming up like this structure.

```public static final char[][] chs = {{'6', '9'}, {'9', '6'}, {'1', '1'}, {'8', '8'}, {'0', '0'}};

public static List<String> findStrobogrammatic(int n) {
List<String> ans = new ArrayList<String>();
if ((n & 1) == 1) {
findHelper(ans, new StringBuffer("1"), 1, n);
findHelper(ans, new StringBuffer("0"), 1, n);
findHelper(ans, new StringBuffer("8"), 1, n);
}
else {
findHelper(ans, new StringBuffer(), 0, n);
}
return ans;
}

public static void findHelper(List<String> ans, StringBuffer buf, int pos, int n) {
if (buf.length() >= n && buf.charAt(0) != '0') {
return;
}
for (int i = 0; i < 4; i++) {
buf.insert(0, chs[i]);
buf.append(chs[i]);
findHelper(ans, buf, pos + 2, n);
buf.deleteCharAt(0);
buf.deleteCharAt(buf.length() - 1);
}
}```

Naturally, I come up with solution to Strobogrammatic Number III: 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.

Solution. For this problem, key is to compare the buf and lo, buf and high by below function. If buf is between lo and high, then ans++.

```public static int compare(String str1, String str2) {
if (str1.length() != str2.length())
return str1.length() - str2.length();
int n = str1.length();
for (int i = 0; i < n; i++) {
if (str1.charAt(i) != str2.charAt(i)) {
return str1.charAt(i) - str2.charAt(i);
}
}
return 0;
}

```

Check my code on github: StrobogrammaticII(solution1)StrobogrammaticII(solution2)StrobogrammaticIII