[LeetCode] 93. Restore IP Addresses

轉自LeetCode

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

<Solution>

這題是要將字串組合成合法的 ip address

雖然字串問題通常會先想到 dp，但是這題是在求所有可能的組合

這時候反而是要用 DFS 的想法

解題想法如下（參考資料）

• 將 s 分成四段，每段的長度是 1 到 3，並用遞迴處理每一段

• 每一段都要檢查是否合法，數值範圍要在 0 - 255，且不能有 010，011這種情況出現

• 當四段都處理完後，還要確保 s 裡面的字元都有用到，不然就代表 s 包含過多字元

code 如下

	class Solution {
	private:
	vector<string> ans;
	public:
	vector<string> restoreIpAddresses(string s) {
	//> dfs
	dfs(s, 0, "");
	return ans;
	}
	void dfs(const string &s, const int &section, const string &out) {
	if(section == 4) {
	//> all char in s must be used
	if(s.empty()) {
	ans.push_back(out);
	}
	return;
	}
	for(int i = 1; i <= 3; i++) {
	string tmpS = s.substr(0, i);
	if(s.size() >= i && isValid(tmpS)) {
	if(section == 3) {
	dfs(s.substr(i), section+1, out + tmpS);
	}
	else {
	dfs(s.substr(i), section+1, out + tmpS + ".");
	}
	}
	}
	}
	bool isValid(const string &str) {
	//> eg. "010" is not valid
	if(str.size() > 1 && str[0] == '0') {
	return false;
	}
	int num = stoi(str.c_str());
	return num <= 255;
	}
	};

view raw restoreIpAddress_1.cpp hosted with ❤ by GitHub

還有更精簡的寫法，可以把 isValid() 拿掉

• 當遞迴的過程中，s 的長度不足 1 的時候，就直接結束

• i == to_string(num).length()，這個是用來濾掉 "010"，"011" 這種字串

舉例 : "010"，當 int num = stoi("010")，num = 10，這時候 i = 3，因為當下處理的字串長度是 3
然後使用 to_string(num) 會得到 "10"，這時候長度反而變 2，因為前綴的0被拿掉了
所以可以使用 i == to_string(num).length() 來過濾有前綴無意義 0 的字串

code 如下

	class Solution {
	private:
	vector<string> ans;
	public:
	vector<string> restoreIpAddresses(string s) {
	//> dfs
	dfs(s, 0, "");
	return ans;
	}
	void dfs(const string &s, const int &section, const string &out) {
	if(section == 4) {
	//> all char in s must be used
	if(s.empty()) {
	ans.push_back(out);
	}
	return;
	}
	for(int i = 1; i <= 3; i++) {
	if(s.size() < i) {
	break;
	}
	string tmpS = s.substr(0, i);
	int num = stoi(tmpS);
	//> check valid ip address
	if(num <= 255 && i == to_string(num).length()) {
	dfs(s.substr(i), section+1, out + tmpS + ((section == 3) ? "" : "."));
	}
	}
	}
	};

view raw restoreIpAddress_2.cpp hosted with ❤ by GitHub

那因為這題的情況不會很多，IP 固定會有四段，每段長度 1 到 3

所以就用暴力法，四個 for 迴圈下去組合

然後也運用上面提到的 stoi 之後的數字，再用 to_string 轉回字串，其長度可以用來濾掉 "010" 這種情況的方式

code 如下

	class Solution {
	public:
	vector<string> restoreIpAddresses(string s) {
	vector<string> ans;
	string out;
	for(int a = 1; a < 4; a++) {
	for(int b = 1; b < 4; b++) {
	for(int c = 1; c < 4; c++) {
	for(int d = 1; d < 4; d++) {
	//> all char in s are used
	if((a+b+c+d) == s.length()) {
	int numA = stoi(s.substr(0,a));
	int numB = stoi(s.substr(a,b));
	int numC = stoi(s.substr(a+b,c));
	int numD = stoi(s.substr(a+b+c,d));
	//> check is valid IP address or not
	if(numA <= 255 && numB <= 255 && numC <= 255 && numD <= 255) {
	out = to_string(numA) + "." + to_string(numB) + "." + to_string(numC) + "." + to_string(numD);
	//> there are only three extra '.' in out
	if(out.length() == s.length() + 3) {
	ans.push_back(out);
	}
	}
	}
	}
	}
	}
	}
	return ans;
	}
	};

view raw restoreIpAddress_3.cpp hosted with ❤ by GitHub