Strobogrammatic Number II
Total Accepted: 6692 Total Submissions: 20034 Difficulty: Medium
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"].
思路
- DFS
- 自己写的coding style很不好,就不要参考了
public class Solution {
Map<Character, Character> map = new HashMap<Character, Character>();
int[] nums = new int[]{0, 1, 8, 6, 9};
public List<String> findStrobogrammatic(int n) {
List<String> result = new ArrayList<String>();
StringBuilder string = new StringBuilder();
if (n == 1) {
result.add("0");
result.add("1");
result.add("8");
return result;
}
map.put('6', '9');
map.put('9', '6');
map.put('1', '1');
map.put('0', '0');
map.put('8', '8');
dfs(result, string, n, 1);
return result;
}
public void dfs(List<String> result, StringBuilder string, int n, int index) {
StringBuilder sb = new StringBuilder(string);
if (index - 1 == n / 2) {
if (n % 2 == 0) {
for (int i = sb.length() - 1; i >= 0; i--) {
char newChar = map.get(sb.charAt(i));
sb.append(newChar);
}
if (sb.length() == n && sb.charAt(0) != '0' ) {
result.add(new String(sb.toString()));
}
} else {
for (int i = 0; i <= 2; i++) {
StringBuilder temp = new StringBuilder(sb);
temp.append(Integer.toString(nums[i]));
for (int k = temp.length() - 2; k >= 0; k--) {
char newChar = map.get(temp.charAt(k));
temp.append(newChar);
}
if (temp.length() == n && temp.charAt(0) != '0') {
result.add(new String(temp.toString()));
}
}
}
return;
}
for (int i = index; i <= n / 2; i++) {
for (int j = 0; j < nums.length; j++) {
string.append(Integer.toString(nums[j]));
dfs(result, string, n, i + 1);
string.deleteCharAt(string.length() - 1);
}
}
}
}
更快的DFS
- 通过char array,避免了string的操作
public class Solution {
public List<String> findStrobogrammatic(int n) {
Map<Character, Character> map = new HashMap<Character, Character>();
map.put('0', '0');
map.put('1', '1');
map.put('6', '9');
map.put('8', '8');
map.put('9', '6');
List<String> result = new ArrayList<String>();
char[] buffer = new char[n];
dfs(n, 0, buffer, result, map);
return result;
}
private void dfs(int n, int index, char[] buffer, List<String> result, Map<Character, Character> map) {
if (n == 0) {
return;
}
if (index == (n + 1) / 2) {
result.add(String.valueOf(buffer));
return;
}
for (Character c : map.keySet()) {
if (index == 0 && n > 1 && c == '0') {
continue;
}
if (index == n / 2 && (c == '6' || c == '9')) {
continue;
}
buffer[index] = c;
buffer[n - 1 - index] = map.get(c);
dfs(n, index + 1, buffer, result, map);
}
}
}
一个简洁的办法
public List<String> findStrobogrammatic(int n) {
return helper(n, n);
}
List<String> helper(int n, int m) {
if (n == 0) return new ArrayList<String>(Arrays.asList(""));
if (n == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8"));
List<String> list = helper(n - 2, m);
List<String> res = new ArrayList<String>();
for (int i = 0; i < list.size(); i++) {
String s = list.get(i);
if (n != m) res.add("0" + s + "0");
res.add("1" + s + "1");
res.add("6" + s + "9");
res.add("8" + s + "8");
res.add("9" + s + "6");
}
return res;
}