Restore IP Addresses

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> out;
        vector<string> parts;
        function<void(int)> dfs = [&](int start) {
            if (parts.size() == 4) {
                if (start == (int)s.size())
                    out.push_back(parts[0] + "." + parts[1] + "." + parts[2] + "." + parts[3]);
                return;
            }
            for (int len = 1; len <= 3 && start + len <= (int)s.size(); ++len) {
                string seg = s.substr(start, len);
                if ((seg[0] == '0' && len > 1) || stoi(seg) > 255) continue;
                parts.push_back(seg);
                dfs(start + len);
                parts.pop_back();
            }
        };
        dfs(0);
        return out;
    }
};

import "strconv"

func restoreIpAddresses(s string) []string {
    out := []string{}
    parts := []string{}
    var dfs func(start int)
    dfs = func(start int) {
        if len(parts) == 4 {
            if start == len(s) {
                out = append(out, parts[0]+"."+parts[1]+"."+parts[2]+"."+parts[3])
            }
            return
        }
        for length := 1; length <= 3 && start+length <= len(s); length++ {
            seg := s[start : start+length]
            if seg[0] == '0' && length > 1 {
                continue
            }
            n, _ := strconv.Atoi(seg)
            if n > 255 {
                continue
            }
            parts = append(parts, seg)
            dfs(start + length)
            parts = parts[:len(parts)-1]
        }
    }
    dfs(0)
    return out
}

from typing import List

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        out: List[str] = []
        parts: List[str] = []

        def dfs(start: int) -> None:
            if len(parts) == 4:
                if start == len(s):
                    out.append('.'.join(parts))
                return
            for length in range(1, 4):
                if start + length > len(s):
                    break
                seg = s[start:start + length]
                if seg[0] == '0' and length > 1:
                    continue
                if int(seg) > 255:
                    continue
                parts.append(seg)
                dfs(start + length)
                parts.pop()

        dfs(0)
        return out

function restoreIpAddresses(s) {
    const out = [];
    const parts = [];
    const dfs = (start) => {
        if (parts.length === 4) {
            if (start === s.length) out.push(parts.join('.'));
            return;
        }
        for (let length = 1; length <= 3 && start + length <= s.length; length++) {
            const seg = s.substring(start, start + length);
            if (seg[0] === '0' && length > 1) continue;
            if (parseInt(seg, 10) > 255) continue;
            parts.push(seg);
            dfs(start + length);
            parts.pop();
        }
    };
    dfs(0);
    return out;
}

class Solution {
    private List<String> out;
    private List<String> parts;
    private String s;

    public List<String> restoreIpAddresses(String s) {
        this.s = s;
        out = new ArrayList<>();
        parts = new ArrayList<>();
        dfs(0);
        return out;
    }

    private void dfs(int start) {
        if (parts.size() == 4) {
            if (start == s.length()) out.add(String.join(".", parts));
            return;
        }
        for (int length = 1; length <= 3 && start + length <= s.length(); length++) {
            String seg = s.substring(start, start + length);
            if (seg.charAt(0) == '0' && length > 1) continue;
            if (Integer.parseInt(seg) > 255) continue;
            parts.add(seg);
            dfs(start + length);
            parts.remove(parts.size() - 1);
        }
    }
}

function restoreIpAddresses(s: string): string[] {
    const out: string[] = [];
    const parts: string[] = [];
    const dfs = (start: number): void => {
        if (parts.length === 4) {
            if (start === s.length) out.push(parts.join('.'));
            return;
        }
        for (let length = 1; length <= 3 && start + length <= s.length; length++) {
            const seg = s.substring(start, start + length);
            if (seg[0] === '0' && length > 1) continue;
            if (parseInt(seg, 10) > 255) continue;
            parts.push(seg);
            dfs(start + length);
            parts.pop();
        }
    };
    dfs(0);
    return out;
}