Generate IP Addresses

JavaView on GFG

Intuition

Generate all valid IPv4 addresses from a string of digits. Backtracking with 4 parts.

Algorithm

1Backtrack: place 3 dots. Each segment must be valid (0-255, no leading zeros except "0" itself).

Common Pitfalls

•Same as LC 93. Prune: segment > 255 or has leading zero. Exactly 4 segments, all digits used.

Generate IP Addresses.java

Java

// Approach: Backtracking. Try all splits of the string into 4 valid octets (0-255, no leading zeros).
// Time: O(1) bounded Space: O(1)
import java.util.*;

class Solution {
    public ArrayList<String> generateIp(String s) {
        ArrayList<String> result = new ArrayList<>();
        backtrack(s, 0, 0, "", result);
        return result;
    }

    private void backtrack(String s, int index, int parts, String current, ArrayList<String> result) {
        if (parts == 4 && index == s.length()) {
            result.add(current.substring(0, current.length() - 1));
            return;
        }

        if (parts >= 4)
            return;

        for (int len = 1; len <= 3 && index + len <= s.length(); len++) {

            String segment = s.substring(index, index + len);

            if (segment.length() > 1 && segment.startsWith("0"))
                continue;

            int value = Integer.parseInt(segment);

            if (value <= 255)
                backtrack(s, index + len, parts + 1, current + segment + ".", result);
        }
    }
}

Was this solution helpful?