247. Strobogrammatic Number II
https://www.lintcode.com/problem/strobogrammatic-number-ii/description
https://leetcode.com/problems/strobogrammatic-number-ii
Intuition
All possible combinations => DFS
Fill in the string from two ends
Terminate recursion when i reaches (n + 1) / 2
Skip 6, 9 for midpoint of odd length string
Skip 0 for > 1 length string
----https://leetcode.com/problems/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"]---Intuition
All possible combinations => DFS
Fill in the string from two ends
Terminate recursion when i reaches (n + 1) / 2
Skip 6, 9 for midpoint of odd length string
Skip 0 for > 1 length string
Time - O(N)
Space - O(N)
---
Related problems
---
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| /** | |
| * @param n: the length of strobogrammatic number | |
| * @return: All strobogrammatic numbers | |
| */ | |
| public List<String> findStrobogrammatic(int n) { | |
| char [][] map = new char[5][2]; | |
| map[0][0] = '0'; | |
| map[0][1] = '0'; | |
| map[1][0] = '1'; | |
| map[1][1] = '1'; | |
| map[2][0] = '6'; | |
| map[2][1] = '9'; | |
| map[3][0] = '8'; | |
| map[3][1] = '8'; | |
| map[4][0] = '9'; | |
| map[4][1] = '6'; | |
| char[] prefix = new char[n]; | |
| List<String> ans = new ArrayList<String>(); | |
| dfs(n, 0, prefix, map, ans); | |
| return ans; | |
| } | |
| private void dfs(int n, int i, char[] prefix, char[][] map, List<String> ans) { | |
| if (i == (n + 1) / 2) { | |
| ans.add(new String(prefix)); | |
| return; | |
| } | |
| for (int j = 0; j < map.length; j++) { | |
| // At midpoint of odd length string, cannot use 6 or 9 | |
| if (n%2 == 1 && i == n/2 && (map[j][0] == '6' || map[j][0] == '9')) { | |
| continue; | |
| } | |
| // Cannot start with 0 for string longer than 1 | |
| if (n > 1 && i == 0 && map[j][0] == '0') { | |
| continue; | |
| } | |
| prefix[i] = map[j][0]; | |
| prefix[n - i - 1] = map[j][1]; | |
| dfs(n, i + 1, prefix, map, ans); | |
| } | |
| } | |
| } |
---
