Leetcode——93. Restore IP Addresses

本文主要是介绍Leetcode——93. Restore IP Addresses，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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)
https://leetcode.com/problems/restore-ip-addresses/

解答

两个常用的函数：

to_string()：转化为字符串
stoi()：把一个字符串转化为整数

蛮力算法
如下：

class Solution {
public:vector<string> restoreIpAddresses(string s) {vector<string>res;for(int a=1;a<=3;a++)//截取长度for(int b=1;b<=3;b++)for(int c=1;c<=3;c++)for(int d=1;d<=3;d++){if(a+b+c+d==s.length()){int A=stoi(s.substr(0,a));int B=stoi(s.substr(a,b));int C=stoi(s.substr(a+b,c));int D=stoi(s.substr(a+b+c,d));if(A<=255&&B<=255&&C<=255&&D<=255){if((to_string(A)+to_string(B)+to_string(C)+to_string(D)).length()==s.length())//这一行需要添加的原因是：是为了排除以0开头的数字，比如，10.02.1.1（这种情况是不满足的）res.push_back(s.substr(0,a)+"."+s.substr(a,b)+"."+s.substr(a+b,c)+"."+s.substr(a+b+c,d));}}}return res; }
};

或者利用DFS思想

//DFS思想
class Solution {
public:vector<string> restoreIpAddresses(string s) {vector<string>res;restoreIp(res,s,"",0,0);return res;}private:void restoreIp(vector<string>&res,string s,string restored,int count,int idx)//分别是存储结果，原始的字符串s，存储的s，count来计数，idx来表示移动到的下标{if(count>4) return ;if(count==4&&idx==s.length()) res.push_back(restored);for(int i=1;i<=3;i++){if(idx+i>s.length()) break;//+i之后超出，就直接break，后续不再验证string temp=s.substr(idx,i);if((temp[0]=='0'&&i>1)||stoi(temp)>255) continue;//不满足情况，直接跳转到i++restoreIp(res,s,restored+temp+(count==3?"":"."),count+1,idx+i);}}
};