Here, We see Restore IP Addresses LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Restore IP Addresses LeetCode Solution
Table of Contents
Problem Statement
A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0
and 255
(inclusive) and cannot have leading zeros.
- For example,
"0.1.2.201"
and"192.168.1.1"
are valid IP addresses, but"0.011.255.245"
,"192.168.1.312"
and"192.168@1.1"
are invalid IP addresses.
Given a string s
containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s
. You are not allowed to reorder or remove any digits in s
. You may return the valid IP addresses in any order.
Example 1: Input: s = "25525511135" Output: ["255.255.11.135","255.255.111.35"] Example 2: Input: s = "0000" Output: ["0.0.0.0"] Example 3: Input: s = "101023" Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
Restore IP Addresses Leetcode Solution C++
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> result;
string ip;
dfs(s,0,0,ip,result); //paras:string s,start index of s,step(from0-3),intermediate ip,final result
return result;
}
void dfs(string s,int start,int step,string ip,vector<string>& result){
if(start==s.size()&&step==4){
ip.erase(ip.end()-1); //remove the last '.' from the last decimal number
result.push_back(ip);
return;
}
if(s.size()-start>(4-step)*3) return;
if(s.size()-start<(4-step)) return;
int num=0;
for(int i=start;i<start+3;i++){
num=num*10+(s[i]-'0');
if(num<=255){
ip+=s[i];
dfs(s,i+1,step+1,ip+'.',result);
}
if(num==0) break;
}
}
};
Code language: JavaScript (javascript)
Restore IP Addresses Leetcode Solution Java
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> ret = new ArrayList<>();
dfs(s, 0, 0, "", ret);
return ret;
}
private void dfs(String s, int idx, int c, String path, List<String> ret) {
if (c >= 4) {
if (idx == s.length()) {
ret.add(path.substring(0, path.length()-1));
}
return;
}
for (int i = idx+1; i <= s.length(); i++) {
if (isValid(s.substring(idx, i))) {
dfs(s, i, c+1, path + s.substring(idx, i) + '.', ret);
}
}
}
private boolean isValid(String s) {
if (s.startsWith("0") && !s.equals("0")) {
return false;
}
return s.length() < 4 && 0 <= Integer.valueOf(s) && Integer.valueOf(s) < 256;
}
}
Code language: JavaScript (javascript)
Restore IP Addresses Leetcode Solution JavaScript
var restoreIpAddresses = function(s) {
const result = []
function permute(arr, str) {
if(arr.length === 3) {
if(isValid(str)) result.push([...arr, str]);
return;
}
for(let i = 1; i < 4; i++) {
let subStr = str.slice(0, i);
if(!isValid(subStr)) continue;
permute([...arr, subStr], str.slice(i));
}
}
function isValid(str) {
if(+str > 255 || !str.length) return false;
if(str.length >= 2 && str[0] === '0') return false;
return true;
}
permute([], s);
return result.map(x => x.join('.'))
};
Code language: JavaScript (javascript)
Restore IP Addresses Leetcode Solution Python
class Solution(object):
def restoreIpAddresses(self, s):
res = []
self.dfs(s, 0, "", res)
return res
def dfs(self, s, index, path, res):
if index == 4:
if not s:
res.append(path[:-1])
return # backtracking
for i in xrange(1, 4):
if i <= len(s):
if int(s[:i]) <= 255:
self.dfs(s[i:], index+1, path+s[:i]+".", res)
if s[0] == "0": # here should be careful
break