#93复原 IP 地址

import java.util.ArrayList;
import java.util.List;

final class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        if (s.length() < 4 || s.length() > 12) {
            return result;
        }
        backtrack(s, 0, new ArrayList<>(4), result);
        return result;
    }

    private void backtrack(String s, int index, List<String> segments, List<String> result) {
        int segmentsLeft = 4 - segments.size();
        int charactersLeft = s.length() - index;
        if (charactersLeft < segmentsLeft || charactersLeft > segmentsLeft * 3) {
            return;
        }
        if (segmentsLeft == 0) {
            result.add(String.join(".", segments));
            return;
        }

        int value = 0;
        for (int end = index; end < s.length() && end < index + 3; end++) {
            if (end > index && s.charAt(index) == '0') {
                break;
            }
            value = value * 10 + (s.charAt(end) - '0');
            if (value > 255) {
                break;
            }
            segments.add(s.substring(index, end + 1));
            backtrack(s, end + 1, segments, result);
            segments.remove(segments.size() - 1);
        }
    }
}