leetcode 93. Restore IP Addresses

题目描述

93. Restore IP Addresses

代码

回溯法

class Solution {vector<string> res;
public:vector<string> restoreIpAddresses(string s) {string IP;int part = 0;backtracking(s,0,IP,part);return res;}void backtracking(const string &s,int start,string &IP,int &part){if(start == s.size()){if(part == 4)res.push_back(IP);return;}if(part==4)return;int iplen = IP.size();for(int i = start;i < s.size();i++){if(i >start && s[start]=='0')//前导0的数字不考虑break;int temp = atoi(s.substr(start,i-start+1).c_str());if(temp >255)//大于255的不考虑，后面的只会更大，所以breakbreak;IP += (s.substr(start,i-start+1));if(part<3)IP.push_back('.');part++;backtracking(s,i+1,IP,part);IP.resize(iplen);part--;}}
};