Problem:
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"].
Analysis:
This problem is easy. It is just a reverse process of checking a Strobogrammatic number. But I have made following mistakes at this process. Mistake 1:
Wrongly use return when forking search branch. (This would cause other search branches were ignored!)
if (len != n - 2)
cur = num + cur + num;
else
return; Mistake 2:
Wrongly pass around String's reference, without create a new one.
Usually I use String in following way.
helper (..., cur + 'c', ...)
It works totally fine. But this time, I have used the reference in following way, which is totally wrong!
helper(..., cur, ...) To pass around string reference, we should be very careful. Since it is not primitive type, but it was conveniently used as a primitive type. When we use a string, we actually pass it's reference around.
1. Only when we make a change over it, the instance of the old string was discarded and a new string was created.
2. Only when we use a new reference and use "=" sign to copy the content. If we do not pass the new intance as an argument, many problems could occur! 2.1 get the wrong length of the string. Even the cur was actually changed, we keep on get it's original length 0. Thus there is no stop for this program.
...
searchPath(n, nums, "", 0, ret);
..
private void searchPath(int n, char[] nums, String cur, List<String> ret) {
int len = cur.length();
if (len == n) {
ret.add(cur);
return;
}
...
} Errors:
Overflow 2.2 Get wrong result.
To fix above problem, I have tried to pass around the cur's length. But it actually still wrong!! Wrong solution : (update on the same cur all the time)
public class Solution {
public List<String> findStrobogrammatic(int n) {
if (n < 0)
throw new IllegalArgumentException("n is negative!");
List<String> ret = new ArrayList<String> ();
if (n == 0)
return ret;
char[] nums = {'0', '1', '6', '8', '9'};
if (n % 2 == 1) {
for (char num : nums) {
searchPath(n, nums, num + "", 1, ret);
}
} else{
searchPath(n, nums, "", 0, ret);
}
return ret;
} private void searchPath(int n, char[] nums, String cur, int cur_len, List<String> ret) {
if (cur_len == n) {
ret.add(cur);
return;
}
for (char num : nums) {
if (num == '0') {
if (cur_len != n - 2)
cur = num + cur + num;
else
continue;
} else{
if (num == '9')
cur = '9' + cur + '6';
else if (num == '6')
cur = '6' + cur + '9';
else
cur = num + cur + num;
}
searchPath(n, nums, cur, cur_len+2, ret);
}
}
} Error cases:
Input:
2
Output:
["11","6119","861198","98611986"]
Expected:
["11","69","88","96"] As you can see, the "cur" was passed around all the time. Actually we use the same instance all the time.
Fix method:
String next_cur;
for (char num : nums) {
if (num == '0') {
if (len != n - 2)
next_cur = num + cur + num;
else
continue;
} else{
if (num == '9')
next_cur = '9' + cur + '6';
else if (num == '6')
next_cur = '6' + cur + '9';
else
next_cur = num + cur + num;
}
searchPath(n, nums, next_cur, ret);
} Mistake 3:
Another mistake I have made is that I fail to consider "6" and "9" could not be put in the middle when n is odd.
Error case:
Input:
3
Output:
["101","609","808","906","111","619","818","916","161","669","868","966","181","689","888","986","191","699","898","996"]
Expected:
["101","111","181","609","619","689","808","818","888","906","916","986"]
Solution:
public class Solution {
public List<String> findStrobogrammatic(int n) {
if (n < 0)
throw new IllegalArgumentException("n is negative!");
List<String> ret = new ArrayList<String> ();
if (n == 0)
return ret;
char[] core_num = {'0', '1', '8'};
char[] nums = {'0', '1', '6', '8', '9'};
if (n % 2 == 1) {
for (char num : core_num) {
searchPath(n, nums, num + "", ret);
}
} else{
searchPath(n, nums, "", ret);
}
return ret;
}
private void searchPath(int n, char[] nums, String cur, List<String> ret) {
int len = cur.length();
if (len == n) {
ret.add(cur);
return;
}
String next_cur;
for (char num : nums) {
if (num == '0') {
if (len != n - 2)
next_cur = num + cur + num;
else
continue;
} else{
if (num == '9')
next_cur = '9' + cur + '6';
else if (num == '6')
next_cur = '6' + cur + '9';
else
next_cur = num + cur + num;
}
searchPath(n, nums, next_cur, ret);
}
}
}