leetcode

commit 56a916cbf81aa9c1e8dffda9ba95336491bb5c5a
parent ea856cdd5f2aef7e5e0c55e230965b83312d45be
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 30 Mar 2023 22:17:39 +0200

Daily Problem

Diffstat:
A
Problems/0087.cpp
 | 
29
+++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 30 insertions(+), 0 deletions(-)
diff --git a/Problems/0087.cpp b/Problems/0087.cpp
@@ -0,0 +1,29 @@
+class Solution {
+  unordered_map<string, bool> um;
+
+public:
+  bool isScramble(string s1, string s2) {
+    if (um.count(s1 + s2)) return um[s1 + s2];
+    if (s1.size() != s2.size()) return false;
+    if (s1 == s2) return true;
+
+    vector<int> count(128, 0);
+    int n = s1.size();
+    um[s1 + s2] = false;
+
+    for (int i = 0; i < n; i++) count[s1[i]]++, count[s2[i]]--;
+    for (int n : count)
+      if (n) return false;
+
+    for (int k = 1; k < n; k++) {
+      if (isScramble(s1.substr(0, k), s2.substr(0, k)) &&
+              isScramble(s1.substr(k), s2.substr(k)) ||
+          isScramble(s1.substr(0, k), s2.substr(n - k)) &&
+              isScramble(s1.substr(k), s2.substr(0, n - k))) {
+        um[s1 + s2] = true;
+        return true;
+      }
+    }
+    return false;
+  }
+};
diff --git a/README.md b/README.md
@@ -96,6 +96,7 @@ for solving problems.
 |  0082  |   Medium   | [Remove Duplicates from Sorted List II](Problems/0082.cpp)                                       |
 |  0083  |    Easy    | [Remove Duplicates from Sorted List](Problems/0083.cpp)                                          |
 |  0084  |    Hard    | [Largest Rectangle in Histogram](Problems/0084.cpp)                                              |
+|  0087  |    Hard    | [Scramble String](Problems/0087.cpp)                                                             |
 |  0088  |    Easy    | [Merge Sorted Array](Problems/0088.cpp)                                                          |
 |  0090  |   Medium   | [Subsets II](Problems/0090.cpp)                                                                  |
 |  0091  |   Medium   | [Decode Ways](Problems/0091.cpp)                                                                 |