93. Restore IP Addresses

Problem Description

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
• "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.

Examples

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"]

def restoreIpAddresses(s: str) -> List[str]:
    def backtrack(start: int, parts: List[str]):
        if len(parts) == 4 and start == len(s):
            result.append('.'.join(parts))
            return
        
        if len(parts) == 4 or start == len(s):
            return
        
        # Try 1 digit
        parts.append(s[start:start+1])
        backtrack(start + 1, parts)
        parts.pop()
        
        # Try 2 digits if valid
        if start + 1 < len(s) and s[start] != '0':
            parts.append(s[start:start+2])
            backtrack(start + 2, parts)
            parts.pop()
        
        # Try 3 digits if valid
        if (start + 2 < len(s) and s[start] != '0' and 
            int(s[start:start+3]) <= 255):
            parts.append(s[start:start+3])
            backtrack(start + 3, parts)
            parts.pop()
    
    result = []
    backtrack(0, [])
    return result

class Solution {
    private List result;
    private String s;
    
    public List restoreIpAddresses(String s) {
        result = new ArrayList<>();
        this.s = s;
        backtrack(0, new ArrayList<>());
        return result;
    }
    
    private void backtrack(int start, List parts) {
        if (parts.size() == 4 && start == s.length()) {
            result.add(String.join(".", parts));
            return;
        }
        
        if (parts.size() == 4 || start == s.length()) {
            return;
        }
        
        // Try 1 digit
        parts.add(s.substring(start, start + 1));
        backtrack(start + 1, parts);
        parts.remove(parts.size() - 1);
        
        // Try 2 digits if valid
        if (start + 1 < s.length() && s.charAt(start) != '0') {
            parts.add(s.substring(start, start + 2));
            backtrack(start + 2, parts);
            parts.remove(parts.size() - 1);
        }
        
        // Try 3 digits if valid
        if (start + 2 < s.length() && s.charAt(start) != '0') {
            String num = s.substring(start, start + 3);
            if (Integer.parseInt(num) <= 255) {
                parts.add(num);
                backtrack(start + 3, parts);
                parts.remove(parts.size() - 1);
            }
        }
    }
}

class Solution {
private:
    vector result;
    string s;
    
    void backtrack(int start, vector& parts) {
        if (parts.size() == 4 && start == s.length()) {
            string ip;
            for (int i = 0; i < 4; i++) {
                ip += parts[i];
                if (i < 3) ip += ".";
            }
            result.push_back(ip);
            return;
        }
        
        if (parts.size() == 4 || start == s.length()) {
            return;
        }
        
        // Try 1 digit
        parts.push_back(s.substr(start, 1));
        backtrack(start + 1, parts);
        parts.pop_back();
        
        // Try 2 digits if valid
        if (start + 1 < s.length() && s[start] != '0') {
            parts.push_back(s.substr(start, 2));
            backtrack(start + 2, parts);
            parts.pop_back();
        }
        
        // Try 3 digits if valid
        if (start + 2 < s.length() && s[start] != '0') {
            string num = s.substr(start, 3);
            if (stoi(num) <= 255) {
                parts.push_back(num);
                backtrack(start + 3, parts);
                parts.pop_back();
            }
        }
    }
    
public:
    vector restoreIpAddresses(string s) {
        this->s = s;
        vector parts;
        backtrack(0, parts);
        return result;
    }
};

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
    const result = [];
    
    const backtrack = (start, parts) => {
        if (parts.length === 4 && start === s.length) {
            result.push(parts.join('.'));
            return;
        }
        
        if (parts.length === 4 || start === s.length) {
            return;
        }
        
        // Try 1 digit
        parts.push(s.slice(start, start + 1));
        backtrack(start + 1, parts);
        parts.pop();
        
        // Try 2 digits if valid
        if (start + 1 < s.length && s[start] !== '0') {
            parts.push(s.slice(start, start + 2));
            backtrack(start + 2, parts);
            parts.pop();
        }
        
        // Try 3 digits if valid
        if (start + 2 < s.length && s[start] !== '0') {
            const num = s.slice(start, start + 3);
            if (parseInt(num) <= 255) {
                parts.push(num);
                backtrack(start + 3, parts);
                parts.pop();
            }
        }
    };
    
    backtrack(0, []);
    return result;
};

public class Solution {
    private IList result;
    private string s;
    
    public IList RestoreIpAddresses(string s) {
        result = new List();
        this.s = s;
        Backtrack(0, new List());
        return result;
    }
    
    private void Backtrack(int start, List parts) {
        if (parts.Count == 4 && start == s.Length) {
            result.Add(string.Join(".", parts));
            return;
        }
        
        if (parts.Count == 4 || start == s.Length) {
            return;
        }
        
        // Try 1 digit
        parts.Add(s.Substring(start, 1));
        Backtrack(start + 1, parts);
        parts.RemoveAt(parts.Count - 1);
        
        // Try 2 digits if valid
        if (start + 1 < s.Length && s[start] != '0') {
            parts.Add(s.Substring(start, 2));
            Backtrack(start + 2, parts);
            parts.RemoveAt(parts.Count - 1);
        }
        
        // Try 3 digits if valid
        if (start + 2 < s.Length && s[start] != '0') {
            string num = s.Substring(start, 3);
            if (int.Parse(num) <= 255) {
                parts.Add(num);
                Backtrack(start + 3, parts);
                parts.RemoveAt(parts.Count - 1);
            }
        }
    }
}