0093 - Restore IP Addresses (Medium)

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

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

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

// ideas:
// A valid ip address would have 4 parts separated by dots
// we iterate through `s` to insert 3 dots and separate the string into 4 segments
// for each segment, we check if it is valid
// if all 4 segments are valid, we combine those 4 segments with dots and push to the answer

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ans;
        int n = s.size();
        // iterate `s` - place 3 dots to have 4 segments
        // [seg1].[seg2].[seg3].[seg4]
        // 1st dot - we just need to run it 3 times at most
        // e.g. for 255, we can place the first dot at `2.55`, `25.5` or `255.`
        for (int i = 1; i < 4 && i < n; i++) {
            // we place the 2nd dot in a similar way
            for (int j = i + 1; j < i + 4 && j < n; j++) {
                // we place the 3rd dot in a similar way
                for (int k = j + 1; k < j + 4 && k < n; k++) {
                    // now we can separate into 4 segments
                    string seg1 = s.substr(0, i),
                           seg2 = s.substr(i, j - i),
                           seg3 = s.substr(j, k - j),
                           seg4 = s.substr(k);
                    // for each segment, check if it is valid
                    if (ok(seg1) && ok(seg2) && ok(seg3) && ok(seg4)) {
                        // if so, we build the ip address and push to answer
                        ans.push_back(seg1 + "." + seg2 + "." + seg3 + "." + seg4);
                    }
                }
            }
        }
        return ans;
    }

    // check if a given IP address segment is valid
    // 192 -> true
    // 312 -> false
    bool ok(string s) {
        // string length > 3 is not a valid IP address segment
        if (s.size() > 3 ||
            // empty segment is not valid
            s.size() == 0 ||
            // if the first character is 0, we cannot have something like 0x, 0xx
            (s[0] == '0' && s.size() > 1) ||
            // segment is out of range
            stoi(s) > 255
           ) {
            return false;
        }
        return true;
    }
};

// ideas:
// A valid ip address would have 4 parts separated by dots
// we iterate through `s` to insert 3 dots and separate the string into 4 segments
// for each segment, we check if it is valid
// if all 4 segments are valid, we combine those 4 segments with dots and push to the answer
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        int n = s.length();
        // iterate `s` - place 3 dots to have 4 segments
        // [seg1].[seg2].[seg3].[seg4]
        // 1st dot - we just need to run it 3 times at most
        // e.g. for 255, we can place the first dot at `2.55`, `25.5` or `255.`
        for (int i = 1; i < 4 && i < n; i++) {
            // we place the 2nd dot in a similar way
            for (int j = i + 1; j < i + 4 && j < n; j++) {
                // we place the 3rd dot in a similar way
                for (int k = j + 1; k < j + 4 && k < n; k++) {
                    // now we can separate into 4 segments
                    String seg1 = s.substring(0, i),
                           seg2 = s.substring(i, j),
                           seg3 = s.substring(j, k),
                           seg4 = s.substring(k);
                    // for each segment, check if it is valid
                    if (ok(seg1) && ok(seg2) && ok(seg3) && ok(seg4)) {
                        // if so, we build the ip address and push to answer
                        ans.add(seg1 + "." + seg2 + "." + seg3 + "." + seg4);
                    }
                }
            }
        }
        return ans;
    }

    // check if a given IP address segment is valid
    // 192 -> true
    // 312 -> false
    private boolean ok(String s) {
        // string length > 3 is not a valid IP address segment
        if (s.length() > 3 ||
            // empty segment is not valid
            s.length() == 0 ||
            // if the first character is 0, we cannot have something like 0x, 0xx
            (s.charAt(0) == '0' && s.length() > 1) ||
            // segment is out of range
            Integer.parseInt(s) > 255
           ) {
            return false;
        }
        return true;
    }
}

# ideas:
# A valid ip address would have 4 parts separated by dots
# we iterate through `s` to insert 3 dots and separate the string into 4 segments
# for each segment, we check if it is valid
# if all 4 segments are valid, we combine those 4 segments with dots and push to the answer
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        ans = []
        n = len(s)

        # check if a given IP address segment is valid
        # 192 -> true
        # 312 -> false
        def ok(seg: str) -> bool:
            # string length > 3 is not a valid IP address segment
            # empty segment is not valid
            # if the first character is 0, we cannot have something like 0x, 0xx
            # segment is out of range
            if len(seg) > 3 or len(seg) == 0 or (seg[0] == '0' and len(seg) > 1) or int(seg) > 255:
                return False
            return True

        # iterate `s` - place 3 dots to have 4 segments
        # [seg1].[seg2].[seg3].[seg4]
        # 1st dot - we just need to run it 3 times at most
        # e.g. for 255, we can place the first dot at `2.55`, `25.5` or `255.`
        for i in range(1, 4):
            # we place the 2nd dot in a similar way
            for j in range(i + 1, i + 4):
                # we place the 3rd dot in a similar way
                for k in range(j + 1, j + 4):
                    # now we can separate into 4 segments
                    seg1, seg2, seg3, seg4 = s[:i], s[i:j], s[j:k], s[k:]
                    # for each segment, check if it is valid
                    if ok(seg1) and ok(seg2) and ok(seg3) and ok(seg4):
                        # if so, we build the ip address and push to answer
                        ans.append(seg1 + "." + seg2 + "." + seg3 + "." + seg4)
        return ans

// ideas:
// A valid ip address would have 4 parts separated by dots
// we iterate through `s` to insert 3 dots and separate the string into 4 segments
// for each segment, we check if it is valid
// if all 4 segments are valid, we combine those 4 segments with dots and push to the answer

impl Solution {
    fn restore_ip_addresses(s: String) -> Vec<String> {
        let mut ans = vec![];
        let n = s.len();
        // iterate `s` - place 3 dots to have 4 segments
        // [seg1].[seg2].[seg3].[seg4]
        // 1st dot - we just need to run it 3 times at most
        // e.g. for 255, we can place the first dot at `2.55`, `25.5` or `255.`
        for i in 1 .. 4 {
            // we place the 2nd dot in a similar way
            for j in i + 1 .. i + 4 {
                // we place the 3rd dot in a similar way
                for k in j + 1 .. j + 4 {
                    if k < n {
                        // now we can separate into 4 segments
                        let seg1 = &s[..i];
                        let seg2 = &s[i..j];
                        let seg3 = &s[j..k];
                        let seg4 = &s[k..];
                        // for each segment, check if it is valid
                        if Solution::ok(seg1) &&
                           Solution::ok(seg2) &&
                           Solution::ok(seg3) &&
                           Solution::ok(seg4) {
                            // if so, we build the ip address and push to answer
                            ans.push(format!("{}.{}.{}.{}", seg1, seg2, seg3, seg4));
                        }
                    }
                }
            }
        }
        ans
    }

    // check if a given IP address segment is valid
    // 192 -> true
    // 312 -> false
    fn ok(seg: &str) -> bool {
        seg.len() > 0 && seg.len() <= 3 && !(seg.starts_with('0') && seg.len() > 1) && seg.parse::<u32>().unwrap() <= 255
    }
}