commit e1f1ff2d2d34069c7df87c656f691c7c61dcded3
parent 5875d818b502313739a0070c90d54a31d4a6f4af
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 18 Dec 2023 14:27:00 +0000
Daily Problem and 2 Random Problems
Diffstat:
4 files changed, 174 insertions(+), 0 deletions(-)
diff --git a/Problems/0127.cpp b/Problems/0127.cpp
@@ -0,0 +1,91 @@
+// Make graph and search, interesting similarity test, O(n^2)
+class Solution {
+ static uint64_t convert(const string &word) {
+ uint64_t res = 0;
+ for (const char c : word)
+ res = (res << 5) + (c & 0x1F);
+ return res;
+ }
+
+ static bool connected(uint64_t a, uint64_t b) {
+ const uint64_t cmp = max(a, b) ^ min(a, b);
+ return (63 - __builtin_clzll(cmp)) / 5 == __builtin_ctzll(cmp) / 5;
+ }
+
+ public:
+ int ladderLength(const string &beginWord, const string &endWord, const vector<string> &wordList) const {
+ static uint64_t val[5001];
+ const int n = wordList.size();
+ vector<vector<int>> adj(n + 1);
+
+ for (int i = 0; i < n; i++)
+ val[i] = convert(wordList[i]);
+ val[n] = convert(beginWord);
+
+ int m = -1;
+ for (int i = 0; i < n; i++) {
+ if (wordList[i] == beginWord) continue;
+ if (wordList[i] == endWord) m = i;
+ for (int j = i + 1; j <= n; j++) {
+ if (connected(val[i], val[j])) {
+ adj[i].push_back(j);
+ adj[j].push_back(i);
+ }
+ }
+ }
+
+ if (m == -1) return 0;
+
+ unordered_set<int> seen;
+ queue<int> q;
+ q.push(n);
+ seen.insert(n);
+ for (int lvl = 1; !q.empty(); lvl++) {
+ for (int k = q.size(); k > 0; k--) {
+ const int crnt = q.front();
+ q.pop();
+ for (const int next : adj[crnt]) {
+ if (seen.count(next)) continue;
+ if (next == m) return lvl + 1;
+ seen.insert(next);
+ q.push(next);
+ }
+ }
+ }
+
+ return 0;
+ }
+};
+
+// Optimal solution, by trying all similar strings, O(m*n)
+class Solution {
+ public:
+ int ladderLength(const string &beginWord, const string &endWord, const vector<string> &wordList) const {
+ const int n = wordList.size(), m = wordList[0].size();
+ unordered_set<string> list(begin(wordList), end(wordList));
+ unordered_set<string> seen;
+ queue<string> q;
+
+ q.push(beginWord);
+ seen.insert(beginWord);
+ for (int lvl = 1; !q.empty(); lvl++) {
+ for (int k = q.size(); k > 0; k--) {
+ const string &crnt = q.front();
+ for (int i = 0; i < m; i++) {
+ for (int c = 'a'; c <= 'z'; c++) {
+ string next = crnt;
+ next[i] = c;
+ if (list.count(next) && !seen.count(next)) {
+ if (next == endWord) return lvl + 1;
+ seen.insert(next);
+ q.push(next);
+ }
+ }
+ }
+ q.pop();
+ }
+ }
+
+ return 0;
+ }
+};
diff --git a/Problems/0212.cpp b/Problems/0212.cpp
@@ -0,0 +1,58 @@
+class Solution {
+ struct Node {
+ Node(){};
+ Node *children[27] = {nullptr};
+ bool &terminate = reinterpret_cast<bool &>(children[0]);
+
+ void insert(const string &s) {
+ Node *crnt = this;
+ for (const char c : s) {
+ const int idx = c & 0x1F;
+ if (!crnt->children[idx]) crnt->children[idx] = new Node();
+ crnt = crnt->children[idx];
+ }
+ crnt->terminate = true;
+ }
+ };
+
+ int n, m;
+ vector<string> res;
+
+ void dfs(vector<vector<char>> &board, Node *trie, int x, int y) {
+ const char c = board[x][y], idx = c & 0x1F;
+ if (c == '#' || !(trie = trie->children[idx])) return;
+
+ res.back().push_back(c);
+ if (trie->terminate) {
+ res.push_back(res.back());
+ trie->terminate = false;
+ }
+
+ board[x][y] = '#';
+ if (x > 0) dfs(board, trie, x - 1, y);
+ if (y > 0) dfs(board, trie, x, y - 1);
+ if (x < n) dfs(board, trie, x + 1, y);
+ if (y < m) dfs(board, trie, x, y + 1);
+ board[x][y] = c;
+ res.back().pop_back();
+ }
+
+ public:
+ vector<string> findWords(vector<vector<char>> &board, const vector<string> &words) {
+ Node *trie = new Node();
+ for (const string &word : words)
+ trie->insert(word);
+
+ n = board.size() - 1, m = board[0].size() - 1;
+
+ res.push_back("");
+ for (int i = 0; i <= n; i++) {
+ for (int j = 0; j <= m; j++) {
+ dfs(board, trie, i, j);
+ }
+ }
+ res.pop_back();
+
+ return res;
+ }
+};
diff --git a/Problems/1913.cpp b/Problems/1913.cpp
@@ -0,0 +1,22 @@
+class Solution {
+ public:
+ int maxProductDifference(vector<int> &nums) const {
+ sort(begin(nums), begin(nums) + 4);
+ int a = nums[0], b = nums[1];
+ int c = nums[2], d = nums[3];
+ for (int i = 4; i < nums.size(); i++) {
+ if (nums[i] > d) {
+ c = d;
+ d = nums[i];
+ } else if (nums[i] > c) {
+ c = nums[i];
+ } else if (nums[i] < a) {
+ b = a;
+ a = nums[i];
+ } else if (nums[i] < b) {
+ b = nums[i];
+ }
+ }
+ return c * d - a * b;
+ }
+};
diff --git a/README.md b/README.md
@@ -144,6 +144,7 @@ for solving problems.
| 0122 | Medium | [Best Time to Buy and Sell Stock II](Problems/0122.cpp) |
| 0124 | Hard | [Binary Tree Maximum Path Sum](Problems/0124.cpp) |
| 0125 | Easy | [Valid Palindrome](Problems/0125.cpp) |
+| 0127 | Hard | [Word Ladder](Problems/0127.cpp) |
| 0128 | Medium | [Longest Consecutive Sequence](Problems/0128.cpp) |
| 0129 | Medium | [Sum Root to Leaf Numbers](Problems/0129.cpp) |
| 0130 | Medium | [Surrounded Regions](Problems/0130.cpp) |
@@ -212,6 +213,7 @@ for solving problems.
| 0209 | Medium | [Minimum Size Subarray Sum](Problems/0209.cpp) |
| 0210 | Medium | [Course Schedule II](Problems/0210.cpp) |
| 0211 | Medium | [Design Add and Search Words Data Structure](Problems/0211.cpp) |
+| 0212 | Hard | [Word Search II](Problems/0212.cpp) |
| 0213 | Medium | [House Robber II](Problems/0213.cpp) |
| 0215 | Medium | [Kth Largest Element in an Array](Problems/0215.cpp) |
| 0216 | Medium | [Combination Sum III](Problems/0216.cpp) |
@@ -851,6 +853,7 @@ for solving problems.
| 1905 | Medium | [Count Sub Islands](Problems/1905.cpp) |
| 1907 | Medium | [Count Salary Categories](Problems/1907.cpp) |
| 1910 | Medium | [Remove All Occurrences of a Substring](Problems/1910.cpp) |
+| 1913 | Medium | [Maximum Product Difference Between Two Pairs](Problems/1913.cpp) |
| 1921 | Medium | [Eliminate Maximum Number of Monsters](Problems/1921.cpp) |
| 1926 | Medium | [Nearest Exit from Entrance in Maze](Problems/1926.cpp) |
| 1930 | Medium | [Unique Length-3 Palindromic Subsequences](Problems/1930.cpp) |
