复原 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']

题解

JavaScript

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
  const n = s.length;
  const res = [];
  if (n < 4 || n > 12) return res;

  var isValid = function (part) {
    // 每个 part 不能有前导 0
    if (part.length > 1 && part[0] === "0") return false;
    // 每个 part 的数值不能超过 255
    if (Number(part) > 255) return false;
    return true;
  };

  var dfs = function (begin, track) {
    // track 长度为 4 意味着 4 段都找满了
    // 此时还要关注 begin 是否走到了头, 因为要把字符串 s 消耗完
    if (track.length === 4 && begin === n) {
      res.push(track.join("."));
      return;
    }

    // 仅仅找满了 4 段, 但字符串 s 没消耗完
    if (track.length === 4) return;

    // 以  begin 为起点, 往后截 1 - 3 位
    for (let i = 1; i < 4; i++) {
      if (begin + i > s.length) break;
      const part = s.slice(begin, begin + i);
      if (isValid(part)) {
        track.push(part);
        dfs(begin + i, track);
        track.pop();
      }
    }
  };

  dfs(0, []);

  return res;
};

Rust

pub fn restore_ip_addresses(s: String) -> Vec<String> {
    let n = s.len();
    let mut res = Vec::new();
    if n < 4 || n > 12 {
        return res;
    }

    dfs(&s, 0, &mut Vec::new(), &mut res);
    res
}

fn is_valid(part: &str) -> bool {
    if part.len() > 1 && part.starts_with('0') {
        return false;
    }
    if part.parse::<i32>().unwrap() > 255 {
        return false;
    }
    true
}

fn dfs(s: &str, begin: usize, track: &mut Vec<String>, res: &mut Vec<String>) {
    if track.len() == 4 && begin == s.len() {
        res.push(track.join("."));
        return;
    }
    if track.len() == 4 {
        return;
    }

    for i in 1..4 {
        if begin + i > s.len() {
            break;
        }
        let part = &s[begin..begin + i];
        if is_valid(part) {
            track.push(part.to_string());
            dfs(s, begin + i, track, res);
            track.pop();
        }
    }
}