Description:
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Note:
For example: Given "25525511135",return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
Solution:
Analysis and Thinking:
使用分治的思想，通过将原始问题不断缩减为同类性质的小问题，逐一解决，最后再把所有解答集成形成最终答案。这里我们可以用'.'作为分割的标志，将一个初始输入的字符串分割成4个子段，并且能通过4个子段组合成一个符合规定的IP地址。其中每一个子段可能包含1位、2位、或者3位，因此最终需要分类讨论。
Steps:
1.判断输入字符串是否已被全部遍历，且生成了4个段，如果是，停止函数并返回
2.判断字符串总长度是否大于规定的长度，如果是，返回
3.如果输入的字符串只包含1个字符，则加入该字符，且将位置标志加1，子段数量加1，调用自身函数
4.如果输入的字符串包含2个字符，加入这2个字符，将位置标志加2，子段数量加1，调用自身函数
5.如果输入的字符串包含3个字符，加入这3个字符，将位置标志加3，子段数加1，调用自身函数
Codes:
class Solution { public: void ipAddress_solution(string &s,int stringSize,int pos,string &record,vector<string> &result) { if(s.size()-pos>3*(4-num)) return; if(pos==s.size()&&stringSize==4) { result.push_back(record.substr(0,path.size()-1)); return; } if(pos<s.size()) { record=record+s.substr(pos,1)+"."; ipAddress_solution(s,stringSize+1,pos+1,record,result); record=record.substr(0,record.size()-2); } if(pos<s.size()-1&&s[pos]!='0') { record=record+s.substr(pos,2)+"."; ipAddress_solution(s,stringSize+1,pos+2,record,result); record=record.substr(0,record.size()-3); } if(pos<s.size()-2&&s[pos]!='0'&&s.substr(pos,3)<="255") { record=s.substr(pos,3)+"."; ipAddress_solution(s,stringSize+1,pos+3,record,result); record=record.substr(0,record.size()-4); } } vector<string> restoreIpAddress(string s) { vector<string> result; string record; ipAddress_solution(s,0,0,record,result); return result; } };
Results:
