leetcode 93. Restore IP Addresses

题目形貌

93. Restore IP Addresses

代码

回溯法

1. class Solution {
2.     vector<string> res;
3. public:
4.     vector<string> restoreIpAddresses(string s) {
5.         string IP;
6.         int part = 0;
7.         backtracking(s,0,IP,part);
8.         return res;
9.     }
10.     void backtracking(const string &s,int start,string &IP,int &part){
11.         if(start == s.size())
12.         {
13.             if(part == 4)
14.                 res.push_back(IP);
15.             return;
16.         }
18.         if(part==4)
19.             return;
21.         int iplen = IP.size();
22.         for(int i = start;i < s.size();i++){
23.             if(i >start && s[start]=='0')//前导0的数字不考虑
24.                 break;
25.             int temp = atoi(s.substr(start,i-start+1).c_str());
26.             if(temp >255)//大于255的不考虑，后面的只会更大，所以break
27.                 break;
28.             IP += (s.substr(start,i-start+1));
29.             if(part<3)
30.                 IP.push_back('.');
31.             part++;
32.             backtracking(s,i+1,IP,part);
33.             IP.resize(iplen);
34.             part--;
35.         }
36.     }
37. };

复制代码