复原-ip-地址

Tips

题目类型: BackTracking

题目

有效 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成, 且不能含有前导 0), 整数之间用 '.' 分隔. 例如: "0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址, 但是 "0.011.255.245", "192.168.1.312" 是无效 IP 地址.

给定一个只包含数字的字符串 s, 用以表示一个 IP 地址, 返回所有可能的有效 IP 地址, 这些地址可以通过在 s 中插入 '.' 来形成. 你不能重新排序或删除 s 中的任何数字. 你可以按任何顺序返回答案.

提示:

• 1 <= s.length <= 20
• s 仅由数字组成

示例

输入: s = '25525511135'
输出: ['255.255.11.135', '255.255.111.35']

输入: s = '0000'
输出: ['0.0.0.0']

输入: s = '101023'
输出: ['1.0.10.23', '1.0.102.3', '10.1.0.23', '10.10.2.3', '101.0.2.3']

题解

整体的思路是回溯. 首先如果字符串的长度小于 4 或者大于 12, 肯定不可能凑出合法的 IP 地址来, 故过滤掉.

因为 IP 是 4 段, 我们定义一个指针 segmentIdx, 来指向 track 中当前操作的是哪一段.

在递归的结果中, 当 segmentIdx 为 4, 说明 4 段已经找齐了, 但还要判断 begin === n, 也就是这 4 段凑齐的 IP 恰好消耗了字符串, 因为题目要求 IP 地址必须包含 s 的所有字符.

下面是剪枝, 当 segmentIdx 不为 4, 但 begin === n, 说明字符串已经遍历完了, 但还没找齐 4 段, 剪掉.

其次, 要考虑一个特殊情况, 如果前导字符为 0, 它只能独占一位, 举个例子, 1.0.1.11 这个 IP 地址是合法的, 但绝不可能出现 1.01.1.1, 即如果是前导 0, 它只能独占一位. 此时将该 segment 设为 0, 然后递归 dfs, 来执行下一个 segment.

最后就是基本的枚举递归, 具体看代码.

JavaScript

/**
 * @param {string} s
 * @return {string[]}
 */

var restoreIpAddresses = function (s) {
  const n = s.length
  const res = []

  if (n < 4 || n > 12) return res

  const dfs = (begin, segmentIdx, track) => {
    // 如果找到了 4 段 IP 地址并且遍历完了字符串, 那么就是一种答案
    if (segmentIdx === 4) {
      if (begin === n) {
        res.push(track.join('.'))
      }
      return
    }

    // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串, 那么提前回溯
    if (begin === n) return

    // 由于不能有前导零, 如果当前数字为 0, 那么这一段 IP 地址只能为 0
    if (s[begin] === '0') {
      track[segmentIdx] = 0
      dfs(begin + 1, segmentIdx + 1, track)
    }

    // 一般情况, 枚举每一种可能性并递归
    let segment = 0
    for (let i = begin; i < n; i++) {
      segment = segment * 10 + Number(s[i])
      
      // 因为 0 是特殊的, 在上面已经处理了, 所以对于一般情况, 只要在 (0, 255] 这个前开后闭区间即可
      if (segment > 0 && segment <= 255) {
        track[segmentIdx] = segment
        dfs(i + 1, segmentIdx + 1, track)
      } else {
        break
      }
    }
  }

  dfs(0, 0, [])

  return res
}

Rust

pub fn restore_ip_addresses(s: String) -> Vec<String> {
    let mut res: Vec<String> = vec![];
    let arr = s
        .as_bytes()
        .iter()
        .enumerate()
        .fold(vec![], |mut arr, (i, byte)| {
            arr.push((byte - b'0') as i32);
            arr
        });

    if arr.len() < 4 || arr.len() > 12 {
        return res;
    }

    dfs(0, 0, &arr, &mut vec![0; 4], &mut res);

    res
}

fn dfs(
    begin: usize,
    segment_idx: usize,
    arr: &Vec<i32>,
    track: &mut Vec<i32>,
    res: &mut Vec<String>,
) {
    if segment_idx == 4 {
        if begin == arr.len() {
            res.push(
                track
                    .iter()
                    .map(|x| x.to_string())
                    .collect::<Vec<_>>()
                    .join("."),
            );
        }

        return;
    }

    if begin == arr.len() {
        return;
    }

    if arr[begin] == 0 {
        track[segment_idx] = 0;
        dfs(begin + 1, segment_idx + 1, arr, track, res);
    }

    let mut segment = 0;
    for i in begin..arr.len() {
        segment = segment * 10 + arr[i];

        if segment > 0 && segment <= 255 {
            track[segment_idx] = segment;
            dfs(i + 1, segment_idx + 1, arr, track, res);
        } else {
            break;
        }
    }
}