/**
* 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”]
*/
See my solution to the problem here : https://github.com/zcoderz/leetcode/blob/main/src/main/java/logic/FindStrobogrammatic.java
This is a very interesting approach and hence i have included the solution here.
First we need to identify numbers that are symmetric.
1, 8 and 0 are symmetric naturally.
And the pairs {{‘0’, ‘0’}, {‘1’, ‘1’}, {‘6’, ‘9’}, {‘8’, ‘8’}, {‘9’, ‘6’}} are symmetric.
So you can start from the two ends : “0 and end last index” , while creating symmetric combinations recursively and backtracking. When the left and right index are the same, use one of the naturally symmetric numbers. Keep track of the resulting strings whenever the left and right index cross.
void processChars(char[] buffer, int left, int right) {
if (left > right) {
retList.add(new String(buffer));
return;
}
if (left == right) {
for (Character ch : odd) {
buffer[left] = ch;
processChars(buffer, left + 1, right - 1);
}
} else {
for (char[] ch : even) {
//skip numbers that would start with 0
if (ch[0] == '0' && left == 0) continue;
buffer[left] = ch[0];
buffer[right] = ch[1];
processChars(buffer, left + 1, right - 1);
}
}
}