commit 0c45af7adbc5c6cabca3ed186b0a6640b75d1c46
parent 3325cd507088a70f6b5867be6bcbc816dc2dfba0
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sat, 14 Jan 2023 17:59:09 +0100
Daily Problem and some
Diffstat:
4 files changed, 69 insertions(+), 0 deletions(-)
diff --git a/Problems/0884.cpp b/Problems/0884.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+ vector<string> uncommonFromSentences(string s1, string s2) {
+ unordered_map<string, int> um;
+ stringstream ss;
+ string t;
+
+ ss.str(s1);
+ while (ss >> t) um[t]++;
+
+ ss.str(s2);
+ ss.clear();
+ while (ss >> t) um[t]++;
+
+ vector<string> res;
+ for (auto &[str, cnt] : um)
+ if (cnt == 1) res.push_back(str);
+ return res;
+ }
+};
diff --git a/Problems/1061.cpp b/Problems/1061.cpp
@@ -0,0 +1,32 @@
+class UnionFind {
+ int n, cnt = n;
+ vector<int> root;
+
+public:
+ UnionFind(int n) : n(n), root(n) { iota(root.begin(), root.end(), 0); }
+
+ int find(int x) {
+ while (x != root[x]) x = root[x] = root[root[x]];
+ return x;
+ }
+
+ void join(int x, int y) {
+ x = find(x), y = find(y);
+ if (x != y) {
+ if (y > x) swap(x, y);
+ root[x] = y;
+ }
+ }
+};
+
+class Solution {
+public:
+ string smallestEquivalentString(string s1, string s2, string baseStr) {
+ UnionFind uf(126);
+
+ for (int i = 0; i < s1.size(); i++) uf.join(s1[i], s2[i]);
+
+ for (char &c : baseStr) c = uf.find(c);
+ return baseStr;
+ }
+};
diff --git a/Problems/2085.cpp b/Problems/2085.cpp
@@ -0,0 +1,14 @@
+class Solution {
+public:
+ int countWords(vector<string> &words1, vector<string> &words2) {
+ unordered_map<string, int> um1, um2;
+
+ for (auto &t : words1) um1[t]++;
+ for (auto &t : words2) um2[t]++;
+
+ int count = 0;
+ for (auto &[str, cnt] : um1)
+ if (cnt == 1 && um2[str] == 1) count++;
+ return count;
+ }
+};
diff --git a/README.md b/README.md
@@ -201,6 +201,7 @@ for solving problems.
| 0851 | Medium | [Loud and Rich](Problems/0851.cpp) |
| 0872 | Easy | [Leaf-Similar Trees](Problems/0872.cpp) |
| 0876 | Easy | [Middle of the Linked List](Problems/0876.cpp) |
+| 0884 | Easy | [Uncommon Words from Two Sentences](Problems/0884.cpp) |
| 0886 | Medium | [Possible Bipartition](Problems/0886.cpp) |
| 0897 | Easy | [Increasing Order Search Tree](Problems/0897.cpp) |
| 0901 | Medium | [Online Stock Span](Problems/0901.cpp) |
@@ -228,6 +229,7 @@ for solving problems.
| 1042 | Medium | [Flower Planting With No Adjacent](Problems/1042.cpp) |
| 1047 | Easy | [Remove All Adjacent Duplicates In String](Problems/1047.cpp) |
| 1051 | Easy | [Height Checker](Problems/1051.cpp) |
+| 1061 | Medium | [Lexicographically Smallest Equivalent String](Problems/1061.cpp) |
| 1089 | Easy | [Duplicate Zeros](Problems/1089.cpp) |
| 1095 | Easy | [Find Numbers with Even Number of Digits](Problems/1095.cpp) |
| 1099 | Easy | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp) |
@@ -285,6 +287,7 @@ for solving problems.
| 1976 | Medium | [Number of Ways to Arrive at Destination](Problems/1976.cpp) |
| 2039 | Medium | [The Time When the Network Becomes Idle](Problems/2039.cpp) |
| 2073 | Easy | [Time Needed to Buy Tickets](Problems/2073.cpp) |
+| 2085 | Easy | [Count Common Words With One Occurrence](Problems/2085.cpp) |
| 2095 | Medium | [Delete the Middle Node of a Linked List](Problems/2095.cpp) |
| 2101 | Medium | [Detonate the Maximum Bombs](Problems/2101.cpp) |
| 2115 | Medium | [Find All Possible Recipes from Given Supplies](Problems/2115.cpp) |
