LeetCode Q247: 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.

For example,
Given n = 2, return ["11","69","88","96"].

Hint:

1. Try to use recursion and notice that it should recurse with n - 2 instead of n - 1.

Solution:

	class Solution {
	public:
	vector<string> helper(int n, int m) {
	vector<string> res;
	if(n==0){
	res.push_back("");
	return res;
	}
	if(n==1){
	res.push_back("0");
	res.push_back("1");
	res.push_back("8");
	return res;
	}
	vector<string> subRes = helper(n-2, m);
	for(int i=0; i<subRes.size(); i++){
	string tmpStr = subRes[i];
	if(n!=m){
	tmpStr = string("0") + tmpStr + string("0");
	res.push_back(tmpStr);
	}
	tmpStr = subRes[i];
	tmpStr = string("1") + tmpStr + string("1");
	res.push_back(tmpStr);
	tmpStr = subRes[i];
	tmpStr = string("6") + tmpStr + string("9");
	res.push_back(tmpStr);
	tmpStr = subRes[i];
	tmpStr = string("8") + tmpStr + string("8");
	res.push_back(tmpStr);
	tmpStr = subRes[i];
	tmpStr = string("9") + tmpStr + string("6");
	res.push_back(tmpStr);
	}
	return res;
	}
	vector<string> findStrobogrammatic(int n) {
	vector<string> res = helper(n, n);
	return res;
	}
	};

view raw Q247.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	void helper(vector<string>& res, string tmpRes, int k, int n){
	if(k==n){
	res.push_back(tmpRes);
	return;
	}
	string c[] = {"0", "1", "6", "8", "9"};
	for(int i=0; i<5; i++){
	if(k==n-2&&i==0)
	continue;
	string newStr = tmpRes;
	if(i==2)
	newStr = c[2]+newStr+c[4];
	else if(i==4)
	newStr = c[4]+newStr+c[2];
	else
	newStr = c[i]+newStr+c[i];
	helper(res, newStr, k+2, n);
	}
	}
	vector<string> findStrobogrammatic(int n) {
	vector<string> res;
	string c[] = {"0", "1", "6", "8", "9"};
	string tmpRes;
	if(n%2==0)
	helper(res, tmpRes, 0, n);
	else{
	for(int i=0; i<5; i++){
	if(i==2||i==4)
	continue;
	string newRes(c[i]);
	helper(res, newRes, 1, n);
	}
	}
	return res;
	}
	};

view raw Q247Rnd2.cpp hosted with ❤ by GitHub