题目描述
Given a string
s
containing only digits, return all possible valid IP addresses that can be obtained froms
. You can return them in any order.
A valid IP address consists of exactly four integers, each integer is between
0
and255
, 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 “192.168@1.1” 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 |
|
- 时间复杂度: O(n!)
- 空间复杂度: O(n!)
GitHub 代码同步地址: 93.RestoreIpAddresses.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions