8000 not finish yet for RestoreIPAddress Leetcode medium · jacobklo/jalgorithmCPP@fdac657 · GitHub
[go: up one dir, main page]
Skip to content

Commit fdac657

Browse files
author
Jacob Lo
committed
not finish yet for RestoreIPAddress Leetcode medium
1 parent 29e6e7e commit fdac657

File tree

3 files changed

+59
-1
lines changed

3 files changed

+59
-1
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,7 @@ unlike normal projects.
2828
* [MostEleganceString - Hackerrank](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Backtrack/MostEleganceString.h)
2929
* [Davis' Staircase - Hackerrank](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Backtrack/DavisStaircase.h)
3030
* [Add two numbers represented by linked lists - GeeksForGeeks](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Backtrack/AddTwoNumbers.h)
31+
* [RestoreIPAddress - Leetcode - Medium](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Backtrack/RestoreIPAddress.h)
3132
***
3233

3334
#### DataStructure

‎src/Backtrack/RestoreIPAddress.h

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
//
2+
// Created by Jacob Lo on Jan 23, 2019
3+
//
4+
5+
// MEDIUM - NOT FINISH
6+
// https://leetcode.com/problems/restore-ip-addresses/
7+
8+
#pragma once
9+
10+
#include <vector>
11+
#include <sstream>
12+
#include <iostream>
13+
14+
using namespace std;
15+
16+
namespace RestoreIPAddress {
17+
bool checkValidIp ( const string& p1, const string& p2, const string& p3, const string& p4 ) {
18+
return p1.size() <= 3 && p2.size() <= 3 && p3.size() <= 3 && p4.size() <= 3 && stoi(p1) < 256 && stoi(p2) < 256 && stoi(p3) < 256 && stoi(p4) < 256;
19+
}
20+
21+
22+
vector<string> restoreIpAddresses(string s) {
23+
vector<string> holder;
24+
25+
for ( int i = 1; i <= 3 ; i++ ) {
26+
for ( int j = 1 ; j <= 3 ; j++ ) {
27+
for ( int k = 1 ; k <= 3 && (i+j+k) < s.size() ; k++ ) {
28+
string p1 = s.substr(0, i), p2 = s.substr(i, j), p3 = s.substr( i+j , k), p4 = s.substr(i+j+k, s.size());
29+
if ( checkValidIp (p1, p2, p3, p4 )) {
30+
stringstream tmpss;
31+
tmpss << p1 << '.' << p2 << '.' << p3 << '.' << p4;
32+
holder.push_back(tmpss.str());
33+
}
34+
}
35+
}
36+
37+
}
38+
39+
return holder;
40+
}
41+
42+
void test() {
43+
vector<string> ips = {"010010"};
44+
for ( auto ip : ips ) {
45+
vector<string> holder = restoreIpAddresses(ip);
46+
47+
for ( auto s : holder ) {
48+
cout << s << endl;
49+
}
50+
51+
cout << endl << endl;
52+
}
53+
54+
}
55+
}

‎src/CMakeLists.txt

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -57,5 +57,7 @@ add_executable(jalgorithmCPP
5757
String/UniqueEmails.h
5858
Tree/FlattenBinaryTreeList.h
5959
Tree/PopulatingNextRightPointersInEachNode.h
60-
String/Permutations.h)
60+
String/Permutations.h
61+
Backtrack/RestoreIPAddress.h
62+
)
6163

0 commit comments

Comments
 (0)
0