LeetCode OJ:Restore IP Addresses

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)

递归+必要剪枝

class Solution{
public:
	bool isValid(string s){
		if(s.size()>3||!s.size()||s.size()>1&&s[0]=='0')return false;
		int sum=0;
		for(int i=0;i
  
   =0&&sum<=255;
	}
	void dfs(string &s,int start,int count,string path,vector
   
     &result){ if(count>3)return; if(count==3&&isValid(s.substr(start))){ path.append(s.substr(start)); result.push_back(path); return; } for(int i=start;i
    
      restoreIpAddresses(string s){ vector
     
       result; dfs(s,0,0,"",result); return result; } };