# [93. Restore IP Addresses (Medium)](https://leetcode.com/problems/restore-ip-addresses)
<p>A <strong>valid IP address</strong> consists of exactly four integers separated by single dots. Each integer is between <code>0</code> and <code>255</code> (<strong>inclusive</strong>) and cannot have leading zeros.</p>
<ul>
<li>For example, <code>"0.1.2.201"</code> and <code>"192.168.1.1"</code> are <strong>valid</strong> IP addresses, but <code>"0.011.255.245"</code>, <code>"192.168.1.312"</code> and <code>"192.168@1.1"</code> are <strong>invalid</strong> IP addresses.</li>
</ul>
<p>Given a string <code>s</code> containing only digits, return <em>all possible valid IP addresses that can be formed by inserting dots into </em><code>s</code>. You are <strong>not</strong> allowed to reorder or remove any digits in <code>s</code>. You may return the valid IP addresses in <strong>any</strong> order.</p>
<p> </p>
<p><strong class="example">Example 1:</strong></p>
<pre>
<strong>Input:</strong> s = "25525511135"
<strong>Output:</strong> ["255.255.11.135","255.255.111.35"]
</pre>
<p><strong class="example">Example 2:</strong></p>
<pre>
<strong>Input:</strong> s = "0000"
<strong>Output:</strong> ["0.0.0.0"]
</pre>
<p><strong class="example">Example 3:</strong></p>
<pre>
<strong>Input:</strong> s = "101023"
<strong>Output:</strong> ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
</pre>
<p> </p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= s.length <= 20</code></li>
<li><code>s</code> consists of digits only.</li>
</ul>
**Companies**:
[Yandex](https://leetcode.com/company/yandex), [TikTok](https://leetcode.com/company/tiktok), [Oracle](https://leetcode.com/company/oracle), [Amazon](https://leetcode.com/company/amazon), [Microsoft](https://leetcode.com/company/microsoft), [Yahoo](https://leetcode.com/company/yahoo), [Google](https://leetcode.com/company/google), [Facebook](https://leetcode.com/company/facebook), [Apple](https://leetcode.com/company/apple), [ByteDance](https://leetcode.com/company/bytedance), [Cisco](https://leetcode.com/company/cisco), [Arista Networks](https://leetcode.com/company/arista-networks), [Verkada](https://leetcode.com/company/verkada)
**Related Topics**:
[String](https://leetcode.com/tag/string), [Backtracking](https://leetcode.com/tag/backtracking)
**Similar Questions**:
* [IP to CIDR (Medium)](https://leetcode.com/problems/ip-to-cidr)
## Solution 1. Backtracking
Plain backtracking. Maximum depth is 4. Be aware of the cases where ip segment starts with `0` or ip segment is greater than `255`.
```cpp
// OJ: https://leetcode.com/problems/restore-ip-addresses
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> ans;
vector<int> tmp;
function<void(int)> dfs = [&](int i) {
if (i == s.size()) {
if (tmp.size() == 4) {
string ip;
for (int n : tmp) {
if (ip.size()) ip += '.';
ip += to_string(n);
}
ans.push_back(ip);
}
return;
}
for (int j = 0, n = 0; j < (s[i] == '0' ? 1 : 3) && i + j < s.size(); ++j) {
n = n * 10 + s[i + j] - '0';
if (n > 255) break;
tmp.push_back(n);
dfs(i + j + 1);
tmp.pop_back();
}
};
dfs(0);
return ans;
}
};
```
Mopes__
- 粉丝: 2995
- 资源: 648
最新资源
- 基于springboot的茶文化推广系统源码(java毕业设计完整源码).zip
- 基于遗传算法的配电网优化配置 主要内容:分布式电源、无功补偿装置接入配电网,考虑配电网经济性、环境成本和电能质量为目标函数,使用遗传算法进行优化配置,在IEEE33节点系统进行了仿真验证
- 基于springboot的融合多源高校画像数据与协同过滤算法的高考择校推荐系统源码(java毕业设计完整源码+LW).zip
- 三相不平衡潮流计算matlab 本程序采用前推回代法,考虑三相不平衡和互阻抗,可通过改变三相负荷和线路参数构建三相不平衡模型,程序有注释,有参考文档
- 基于springboot的西山区家政服务网站设计与开发源码(java毕业设计完整源码).zip
- 基于计算机视觉与图像处理技术的三维显示系统研究
- 校园自助洗衣服务-JAVA-基于springBoot的校园自助洗衣服务管理系统的设计与实现
- 基于springboot的视频点播系统设计与实现源码(java毕业设计完整源码).zip
- 基于遗传算法优化极限学习机(GA-ELM)的数据分类预测 matlab代码 这段代码主要是一个基于ELM(Extreme Learning Machine)算法的分类器 ELM是一种单隐层前馈神经网
- 基于springboot的财会信息管理系统的分析源码(java毕业设计完整源码).zip
- 基于springboot的资源分享系统源码(java毕业设计完整源码).zip
- 基于遗传算法优化BP神经网络(GA-BP)的数据分类预测 matlab代码
- 校园二手商品交易-JAVA-基于springBoot的校园二手商品交易系统设计与实现(开题报告)
- 基于springboot的踏雪阁民宿订购平台源码(java毕业设计完整源码).zip
- 招聘求职系统-JAVA-基于springBoot的招聘求职系统设计与实现
- 基于springboot的软件技术交流平台设计与实现源码(java毕业设计完整源码).zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈