leetcode

commit 54ba5d4a4aa53aff67359c8382ee8685ad12d165
parent d0f6ac3a11d8c8822d731f9e0fc35e4b0e1e68cf
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 21 Jan 2023 15:07:25 +0100

Daily Problem

Diffstat:
A
Problems/0093.cpp
 | 
42
++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 43 insertions(+), 0 deletions(-)
diff --git a/Problems/0093.cpp b/Problems/0093.cpp
@@ -0,0 +1,42 @@
+class Solution {
+  bool valid(const string &s) {
+    if (s.empty()) return true;
+    return stoi(s) >= 0 && stoi(s) <= 255;
+  }
+
+public:
+  vector<string> restoreIpAddresses(string s) {
+    int n = s.size();
+
+    vector<string> res;
+    string s1, s2, s3, s4;
+    bool e4;
+
+    s1 = "";
+    for (int i = 0; i < n; i++) {
+      s1 += s[i], s2 = "";
+      if (!valid(s1)) break;
+      for (int j = i + 1; j < n; j++) {
+        s2 += s[j], s3 = "";
+        if (!valid(s2)) break;
+        for (int k = j + 1; k < n; k++) {
+          s3 += s[k], s4 = "";
+          if (!valid(s3)) break;
+          for (int l = k + 1; l < n; l++) {
+            s4 += s[l], e4 = false;
+            if (!valid(s4) || (s4.size() >= 2 && s4.front() == '0')) {
+              e4 = true;
+              break;
+            }
+          }
+          if (!e4 && !s4.empty())
+            res.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
+          if (s3.front() == '0') break;
+        }
+        if (s2.front() == '0') break;
+      }
+      if (s1.front() == '0') break;
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -53,6 +53,7 @@ for solving problems.
 |  0070  |    Easy    | [Climbing Stairs](Problems/0070.cpp)                                                             |
 |  0083  |    Easy    | [Remove Duplicates from Sorted List](Problems/0083.cpp)                                          |
 |  0088  |    Easy    | [Merge Sorted Array](Problems/0088.cpp)                                                          |
+|  0093  |   Medium   | [Restore IP Addresses](Problems/0093.cpp)                                                        |
 |  0094  |    Easy    | [Binary Tree Inorder Traversal](Problems/0094.cpp)                                               |
 |  0098  |   Medium   | [Validate Binary Search Tree](Problems/0098.cpp)                                                 |
 |  0099  |   Medium   | [Recover Binary Search Tree](Problems/0099.cpp)                                                  |