1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| // @lc code=start
impl Solution {
/// ## 解题思路
/// - 回溯法
pub fn restore_ip_addresses(s: String) -> Vec<String> {
// s是否为有效ip
fn is_valid_ip(s: &str) -> bool {
// 前导0无效
if s.len() > 1 && &s[0..1] == "0" {
return false;
}
// ip in [0, 256)
match s.parse::<i32>() {
Ok(ip) if ip >= 0 && ip < 256 => true,
_ => false,
}
}
//
fn backtrace(s: &str, dots: &mut Vec<usize>, res: &mut Vec<String>) {
// 终止进一步遍历条件
if dots.len() > 2 {
if is_valid_ip(&s[dots[2]..]) {
res.push(format!(
"{}.{}.{}.{}",
&s[..dots[0]].parse::<i32>().unwrap(),
&s[dots[0]..dots[1]].parse::<i32>().unwrap(),
&s[dots[1]..dots[2]].parse::<i32>().unwrap(),
&s[dots[2]..].parse::<i32>().unwrap()
));
}
return;
}
//
let last_dot = *dots.last().unwrap_or(&0);
for i in last_dot + 1..s.len() {
// 如果当前分隔为非有效ip, 则跳出当前层的试探
if !is_valid_ip(&s[last_dot..i]) {
break;
}
// 找到一个有效的分隔点
dots.push(i); //将其加入到有效集中
// 递归进行下一个分隔符的试探
backtrace(s, dots, res);
// 撤回上一次的试探, 进行下一个试探
dots.pop();
}
}
let mut res = vec![];
backtrace(&s, &mut vec![], &mut res);
res
}
}
// @lc code=end
struct Solution;
|