Restore IP Addresses

Restore IP Addresses.cpp

class Solution {
public:
	vector<string> restoreIpAddresses(string s) {
		vector<string> tmp;
	       	vector<string> result;

		if (s.size() < 4 && s.size() > 12) {
			return result;
		}

		dfs(0, 4, s, tmp, result);

		return result;
	}

	void dfs(int start, int count, string &s, 
		 vector<string> &tmp, vector<string> &result)
	{
		if (start == s.size() && count == 0) {
			string str = concatenate(tmp);
			result.push_back(str);

			return ;
		}

		for (int i = start; i < s.size(); i++) {
			if (true == check(s.substr(start, i-start+1))) {
				tmp.push_back(s.substr(start, i-start+1));
				dfs(i+1, count-1, s, tmp, result);
				tmp.pop_back();
			}
		}
	}

	string concatenate(vector<string> &tmp)
	{
		string str;
		int i;
		for (i = 0; i < tmp.size()-1; i++) {
			str += tmp[i];
			str += ".";
		}
		str += tmp[i];
		return str;
	}

	bool check(string s) {
		stringstream ss(s);
		int num;
		ss >> num;
		if (num > 255) {
			return false;
		}
		
		if (s[0] == '0' && s.size() != 1) {
			return false;
		}
		return true;
	}
};