LeetCode Solutions
247. Strobogrammatic Number II
Time: $O(5^n)$ Space: $O(|\texttt{ans}|)$
class Solution {
public:
vector<string> findStrobogrammatic(int n) {
return helper(n, n);
}
private:
vector<string> helper(int n, int k) {
if (n == 0)
return {""};
if (n == 1)
return {"0", "1", "8"};
vector<string> ans;
for (const string& inner : helper(n - 2, k)) {
if (n < k)
ans.push_back("0" + inner + "0");
ans.push_back("1" + inner + "1");
ans.push_back("6" + inner + "9");
ans.push_back("8" + inner + "8");
ans.push_back("9" + inner + "6");
}
return ans;
}
};
class Solution {
public List<String> findStrobogrammatic(int n) {
return helper(n, n);
}
private List<String> helper(int n, int k) {
if (n == 0)
return new ArrayList<>(Arrays.asList(""));
if (n == 1)
return new ArrayList<>(Arrays.asList("0", "1", "8"));
List<String> ans = new ArrayList<>();
for (final String inner : helper(n - 2, k)) {
if (n < k)
ans.add("0" + inner + "0");
ans.add("1" + inner + "1");
ans.add("6" + inner + "9");
ans.add("8" + inner + "8");
ans.add("9" + inner + "6");
}
return ans;
}
}
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
def helper(n: int, k: int) -> List[str]:
if n == 0:
return ['']
if n == 1:
return ['0', '1', '8']
ans = []
for inner in helper(n - 2, k):
if n < k:
ans.append('0' + inner + '0')
ans.append('1' + inner + '1')
ans.append('6' + inner + '9')
ans.append('8' + inner + '8')
ans.append('9' + inner + '6')
return ans
return helper(n, n)