0%

[Leetcode]93. Restore IP Addresses(C++)

题目描述

题目链接:93. Restore IP Addresses

Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses and “0.011.255.245”, “192.168.1.312” and “[email protected]” are invalid IP addresses.

例子

例子 1

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

例子 2

Input: s = "0000"
Output: ["0.0.0.0"]

例子 3

Input: s = "1111"
Output: ["1.1.1.1"]

Follow Up

Note

Constraints

  • 0 <= s.length <= 3000
  • s consists of digits only.

解题思路

这道题采用回溯法的思路,假设一开始初始化空 IP, 从前往后遍历字符串 s,在遍历每一位 num 时我们有两种选择:

  • 将该位置的数字加到 IP 地址当前最后一位的数字上(IP.back() * 10 + num
  • 或者将该位置加到 IP 地址的新一位(IP.push_back(num)

针对这两种情况有以下情况可以剪枝:

  • 当前 IP 为空或者最后的数字为 0 时,只能执行第一种选择
  • 当 IP 长度超过 4 个数字可以直接返回(针对第一种选择的结果)
  • 当 IP 最后一位数字大于 255 时可以直接返回(针对第二种选择的结果)

遍历到字符串结尾时,只有 IP 恰好为 4 个数字的情况才将其转为 字符串压入结果中。

代码如下:

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
#include <string>
#include <vector>

class Solution {
public:
std::vector<std::string> restoreIpAddresses(std::string s) {
std::vector<int> current_ip;
std::vector<std::string> ip_list;
iterate(s, 0, current_ip, ip_list);
return ip_list;
}

private:
void iterate(const std::string& s, int idx, std::vector<int>& current_ip,
std::vector<std::string>& ip_list) {
if (current_ip.size() > 4 ||
(!current_ip.empty() && current_ip.back() > 255)) {
return;
}

if (idx == s.length()) {
if (current_ip.size() == 4) {
std::string ip = "";
for (int i = 0; i < 3; i++) {
ip += std::to_string(current_ip[i]);
ip += ".";
}
ip += std::to_string(current_ip[3]);
ip_list.push_back(ip);
}
return;
}

// option 1: add new digit to next position
int num = s[idx] - '0';
current_ip.push_back(num);
iterate(s, idx + 1, current_ip, ip_list);
current_ip.pop_back();

// option 2: add new digit to current position only when current
// position is not empty or 0
if (!current_ip.empty() && current_ip.back() != 0) {
current_ip.back() *= 10;
current_ip.back() += num;
iterate(s, idx + 1, current_ip, ip_list);
current_ip.back() /= 10;
}
}
};
  • 时间复杂度: O(n!)
  • 空间复杂度: O(n!)

GitHub 代码同步地址: 93.RestoreIpAddresses.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions