93. Restore IP Addresses Medium

1/**
2 * [93] Restore IP Addresses
3 *
4 * A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.
5 * 
6 * For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "[email protected]" are invalid IP addresses.
7 * 
8 * Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
9 *  
10 * Example 1:
11 * 
12 * Input: s = "25525511135"
13 * Output: ["255.255.11.135","255.255.111.35"]
14 * 
15 * Example 2:
16 * 
17 * Input: s = "0000"
18 * Output: ["0.0.0.0"]
19 * 
20 * Example 3:
21 * 
22 * Input: s = "101023"
23 * Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
24 * 
25 *  
26 * Constraints:
27 * 
28 * 1 <= s.length <= 20
29 * s consists of digits only.
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/restore-ip-addresses/
35// discuss: https://leetcode.com/problems/restore-ip-addresses/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn restore_ip_addresses(s: String) -> Vec<String> {
41        let mut result = vec![];
42        Self::dfs(&s, 0, &mut vec![], &mut result);
43        result
44    }
45
46    fn dfs(s: &String, index: usize, current: &mut Vec<u32>, result: &mut Vec<String>) {
47        if index == s.len() && current.len() == 4 {
48            result.push(current.iter().map(|x| x.to_string()).collect::<Vec<String>>().join("."));
49            return;
50        } else if index == s.len() || current.len() == 4 {
51            return;
52        }
53
54        for i in 1..=3 {
55            if i + index <= s.len() {
56                let next = s[index..i + index].parse::<u32>().unwrap();
57                if next < 256 && (i == 1 || i == 2 && next > 9 || i == 3 && next > 99) {
58                    current.push(next);
59                    Self::dfs(s, index + i, current, result);
60                    current.pop();
61                }
62            }
63        }
64    }
65}
66
67// submission codes end
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn test_93() {
75        println!("Got {:#?}", Solution::restore_ip_addresses("25525511135".to_string()));
76        println!("Got {:#?}", Solution::restore_ip_addresses("101023".to_string()));
77    }
78}
79