【LeetCode】93. Restore IP Addresses(C++)

アドレス:https://leetcode.com/problems/restore-ip-addresses/
タイトル:
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input: “25525511135” Output: [“255.255.11.135”, “255.255.111.35”]
理解:
入力した文字列をすべての可能なIPアドレスに変換するには
実装:
この実現は非常に巧妙であるi,j,k,l各セグメントの長さを表し、最小は1、最大は3であり、加算長さがちょうどsの長さであることを保証する.また、変換後も長さを小さくすることができず、0が発生することを防止する.

class Solution {
public:
	vector<string> restoreIpAddresses(string s) {
		vector<string> res;
		string ans;
		for (int i = 1; i<=3; ++i) 
			for (int j = 1; j<=3; ++j)
				for (int k = 1; k<=3; ++k)
					for (int l = 1; l <= 3; ++l) {
						if (i + j + k + l == s.length()) {
							int tmp1 = stoi(s.substr(0, i));
							int tmp2 = stoi(s.substr(i, j));
							int tmp3 = stoi(s.substr(i + j, k));
							int tmp4 = stoi(s.substr(i + j + k, l));
							if (tmp1 <= 255 && tmp2 <= 255 && tmp3 <= 255 && tmp4 <= 255)
								if ((ans = to_string(tmp1) + "." + to_string(tmp2) + "." + to_string(tmp3) + "." + to_string(tmp4)).length() == s.length() + 3)
									res.push_back(ans);
						}	
					}
		return res;
	}
};