A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.


	For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.


Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

&nbsp;
Example 1:

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]


Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]


Example 3:

Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 20
	s consists of digits only.


class Solution:
    def restoreIpAddresses(self, s: str):
        def isValid(st):
            if(len(st)!=len(str(int(st)))):
                return False
            st = int(st)
            if(st>255 or st<0):
                return False
            return True
        
        validIps = []
        for i in range(1,4):
            s1 = s[:i]
            if(not isValid(s1)):
                continue
            for j in range(i+1, min(len(s), i+4)):
                s2 = s[i:j]
                if(not isValid(s2)):
                    continue
                for k in range(j+1,min(len(s), j+4)):
                    s3 = s[j:k]
                    if(not isValid(s3)):
                        continue
                    s4 = s[k:]
                    if(not isValid(s4)):
                        continue
                    currentIp = s1+"."+s2+"."+s3+"."+s4
                    validIps.append(currentIp)
        return validIps
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();

        int len = s.length();
        for(int i = 1; i < 4 && i < len-2 ; i++ ){
            for(int j = i + 1; j < i + 4 && j < len-1 ; j++ ){
                for(int k = j+1 ; k < j + 4 && k < len ; k++){
                  String s1 = s.substring(0,i);
                  String s2 = s.substring(i,j);
                  String s3 = s.substring(j,k);
                  String s4 = s.substring(k,len);
                  if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4))
                      ans.add(s1+"."+s2+"."+s3+"."+s4);
                }
            }
        }
        return ans;
    }
    boolean isValid(String s){
        if(s.length() > 3 || s.length()==0 || (s.charAt(0)=='0' && s.length()>1) || Integer.parseInt(s) > 255)
           return false;
        return true;
    }
}
class Solution {
public:
    vector<string> res;
    void dfs(string s,int idx,string curr_ip,int cnt)
    {
        if(cnt>4)
            return;
        if(cnt==4&&idx==s.size())
        {
            res.push_back(curr_ip);
           // return;
        }
        for(int i=1;i<4;i++)
        {
            if(idx+i>s.size())
                break;
            string str=s.substr(idx,i);
            if((str[0]=='0'&&str.size()>1)||(i==3&&stoi(str)>=256))
                continue;
            dfs(s,idx+i,curr_ip+str+(cnt==3?"":"."),cnt+1);
        }
    }
    vector<string> restoreIpAddresses(string s)
    {
        dfs(s,0,"",0);
        return res;
        
        
    }
};
var restoreIpAddresses = function(s) {
    const results = [];

    const go = (str, arr) => {
        // if we used every character and have 4 sections, it's a good IP!
        if (str.length === 0 && arr.length === 4) {
            results.push(arr.join('.'));
            return;
        }
        // we already have too many in the array, let's just stop
        if (arr.length >= 4) {
            return;
        }
        // chop off next 3 characters and continue recursing
        if (str.length > 2 && +str.substring(0, 3) < 256 && +str.substring(0, 3) > 0 && str[0] !== '0') {
            go(str.slice(3), [...arr, str.substring(0, 3)]);
        }
        // chop off next 2 characters and continue recursing
        if (str.length > 1 && +str.substring(0, 2) > 0 && str[0] !== '0') {
            go(str.slice(2), [...arr, str.substring(0, 2)]);
        }
        // chop off next 1 character and continue recursing, in this case, starting with 0 is OK
        if (str.length > 0 && +str.substring(0, 1) >= 0) {
            go(str.slice(1), [...arr, str.substring(0, 1)]);
        }
        return;
    }

    go(s, []);

    return results;
};
Restore IP Addresses