LeetCode Q248: Strobogrammatic Number III (hard)

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

Solution:

Starting from arbitrary string with length from len(low to len(high), constructing strobogrammatic while doing DFS. From outside to inside, in each iteration, wrap up current string using a pair of strobogrammatic number. Check whether the string is within the range in between low and high when wrapping is over. 

	class Solution {
	public:
	void dfs(string low, string high, string str, int left, int right, int& count){
	if(str.length()!=1&&str[0]=='0')
	return;
	if(left > right){
	if((str.length()==low.length()&&str.compare(low)<0) ||
	(str.length()==high.length()&&str.compare(high)>0))
	return;
	count++;
	return;
	}
	str[left] = '0', str[right] = '0';
	dfs(low, high, str, left+1, right-1, count);
	str[left] = '1', str[right] = '1';
	dfs(low, high, str, left+1, right-1, count);
	str[left] = '8', str[right] = '8';
	dfs(low, high, str, left+1, right-1, count);
	if(left<right){
	str[left] = '9', str[right] = '6';
	dfs(low, high, str, left+1, right-1, count);
	str[left] = '6', str[right] = '9';
	dfs(low, high, str, left+1, right-1, count);
	}
	}
	int strobogrammaticInRange(string low, string high) {
	int count=0;
	for(int len = low.length(); len<=high.length(); len++){
	string str;
	for(int i=0; i<len; i++)
	str=str+string("9");
	dfs(low, high, str, 0, len-1, count);
	}
	return count;
	}
	};

view raw Q248StrobogrammaticNumberIII.cpp hosted with ❤ by GitHub