题目

题目来源:力扣(LeetCode)

给定一个只包含数字的字符串,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。

例如:”0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址,但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。

示例 1:

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

示例 2:

输入:s = “0000”
输出:[“0.0.0.0”]

示例 3:

输入:s = “1111”
输出:[“1.1.1.1”]

示例 4:

输入:s = “010010”
输出:[“0.10.0.10”,”0.100.1.0”]

示例 5:

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

思路分析

回溯

  1. /**
  2. * @param {string} s
  3. * @return {string[]}
  4. */
  5. var restoreIpAddresses = function (s) {
  6. // SEG_COUNT=4 表示 IP 地址的段数
  7. const SEG_COUNT = 4;
  8. // segments 存储已经搜索过的 IP 地址
  9. const segments = new Array(SEG_COUNT);
  10. const ans = [];
  11. /**
  12. *
  13. * @param s | 数字字符串
  14. * @param segId | IP地址片段
  15. * @param segStart 搜索的起始位置
  16. * @returns
  17. */
  18. const dfs = (s, segId, segStart) => {
  19. // 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
  20. if (segId === SEG_COUNT) {
  21. if (segStart === s.length) {
  22. ans.push(segments.join('.'));
  23. }
  24. return;
  25. }
  26. // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串,那么提前回溯
  27. if (segStart === s.length) {
  28. return;
  29. }
  30. // 由于不能有前导零,如果当前数字为 0,那么这一段 IP 地址只能为 0
  31. if (s.charAt(segStart) === '0') {
  32. segments[segId] = 0;
  33. // 进入下一个IP片段的寻找
  34. dfs(s, segId + 1, segStart + 1);
  35. }
  36. // 一般情况,枚举每一种可能性并递归
  37. let addr = 0;
  38. for (let segEnd = segStart; segEnd < s.length; ++segEnd) {
  39. addr = addr * 10 + (s.charAt(segEnd) - '0'); // (s.charAt(segEnd) - '0') 转换成 int 类型
  40. // 以0x开始的数据表示16进制,0xFF换成十进制为255
  41. if (addr > 0 && addr <= 0xFF) { // 当前IP段数字在0 ~ 255 之间,符合要求
  42. // 设置IP片段的值
  43. segments[segId] = addr;
  44. // 进入下一个IP片段的寻找
  45. dfs(s, segId + 1, segEnd + 1);
  46. } else {
  47. // 不合法,结束本层循环
  48. break;
  49. }
  50. }
  51. }
  52. dfs(s, 0, 0);
  53. return ans;
  54. };