93. Restore IP Addresses

Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses and "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses. 

 

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 = "1111"
Output: ["1.1.1.1"]

Example 4:

Input: s = "010010"
Output: ["0.10.0.10","0.100.1.0"]

Example 5:

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

 

Constraints:

  • 0 <= s.length <= 3000
  • s consists of digits only.

Rust Solution

struct Solution;

impl Solution {
    fn restore_ip_addresses(s: String) -> Vec<String> {
        let n = s.len();
        let mut v: Vec<u8> = vec![0; 4];
        let mut res: Vec<String> = vec![];
        for i in 1..4 {
            if i + 3 > n {
                break;
            }
            if let Ok(a) = s[0..i].parse::<u8>() {
                v[0] = a;
            } else {
                break;
            }
            for j in 1..4 {
                if i + j + 2 > n {
                    break;
                }
                if let Ok(b) = s[i..i + j].parse::<u8>() {
                    v[1] = b;
                } else {
                    break;
                }
                for k in 1..4 {
                    if i + j + k + 1 > n {
                        break;
                    }
                    if let Ok(c) = s[i + j..i + j + k].parse::<u8>() {
                        v[2] = c;
                    } else {
                        break;
                    }
                    for l in 1..4 {
                        if i + j + k + l != n {
                            continue;
                        }
                        if let Ok(d) = s[i + j + k..n].parse::<u8>() {
                            v[3] = d;
                            let ip = format!("{}.{}.{}.{}", v[0], v[1], v[2], v[3]);
                            if ip.len() == n + 3 {
                                res.push(ip);
                            }
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        res
    }
}

#[test]
fn test() {
    let s = "25525511135".to_string();
    let res: Vec<String> = vec_string!["255.255.11.135", "255.255.111.35"];
    assert_eq!(Solution::restore_ip_addresses(s), res);
    let s = "010010".to_string();
    let res: Vec<String> = vec_string!["0.10.0.10", "0.100.1.0"];
    assert_eq!(Solution::restore_ip_addresses(s), res);
}

Having problems with this solution? Click here to submit an issue on github.