leetcode

commit d250236243ac338a7918fcea8415b6582353071b
parent b2bae2ea3099a571005e6c8f79bea05941a27e88
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 13 Feb 2023 18:43:38 +0100

Algorithm II: Day 11

Diffstat:
A
Problems/0017.cpp
 | 
17
+++++++++++++++++
A
Problems/0079.cpp
 | 
45
+++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
5
++++-
A
Templates/bfs_floodfill_recursive.cpp
 | 
27
+++++++++++++++++++++++++++

4 files changed, 93 insertions(+), 1 deletion(-)
diff --git a/Problems/0017.cpp b/Problems/0017.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+  vector<string> letterCombinations(string digits) {
+    vector<string> um = {"abc", "def",  "ghi", "jkl",
+                         "mno", "pqrs", "tuv", "wxyz"},
+                   res = {""};
+
+    for (char d : digits) {
+      vector<string> tmp;
+      for (char l : um[d - '2'])
+        for (const string &s : res) tmp.push_back(s + l);
+      res = tmp;
+    }
+
+    return res.size() > 1 ? res : vector<string>();
+  }
+};
diff --git a/Problems/0079.cpp b/Problems/0079.cpp
@@ -0,0 +1,45 @@
+class Solution {
+  typedef vector<vector<char>> Matrix;
+  typedef vector<vector<bool>> Marked;
+  const vector<pair<int, int>> offsets = {
+      { 0,  1},
+      { 0, -1},
+      { 1,  0},
+      {-1,  0}
+  };
+
+  int n, m;
+  int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
+
+  string word;
+  bool dfs(const Matrix &mat, Marked &mark, int a, int b, int got) {
+    if (got == word.size()) return true;
+
+    mark[a][b] = true;
+    for (auto [oa, ob] : offsets) {
+      int x = a + oa, y = b + ob;
+      if (!valid(x, y) || mark[x][y] || mat[x][y] != word[got]) continue;
+      if (dfs(mat, mark, x, y, got + 1)) return true;
+    }
+    mark[a][b] = false;
+
+    return false;
+  }
+
+public:
+  bool exist(const Matrix &board, string word) {
+    n = board.size(), m = board[0].size();
+    this->word = word;
+
+    Marked visited(n, vector<bool>(m, false));
+
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < m; j++) {
+        if (board[i][j] != word[0]) continue;
+        if (dfs(board, visited, i, j, 1)) return true;
+      }
+    }
+
+    return false;
+  }
+};
diff --git a/README.md b/README.md
@@ -17,7 +17,8 @@ for solving problems.
 
 * [MST from edge priority queue](Templates/MST_pq.cpp)
 * [MST from edge vector](Templates/MST_vector.cpp)
-* [Matrix BFS/Flood fill](Templates/bfs_floodfill.cpp)
+* [Matrix BFS/Flood fill Iterative](Templates/bfs_floodfill.cpp)
+* [Matrix BFS/Flood fill Recursive](Templates/bfs_floodfill_recursive.cpp)
 * [Union Find](Templates/Union_Find.cpp)
 
 ## Problems
@@ -34,6 +35,7 @@ for solving problems.
 |  0013  |    Easy    | [Roman to Integer](Problems/0013.cpp)                                                            |
 |  0014  |    Easy    | [Longest Common Prefix](Problems/0014.cpp)                                                       |
 |  0015  |   Medium   | [3Sum](Problems/0015.cpp)                                                                        |
+|  0017  |   Medium   | [Letter Combinations of a Phone Number](Problems/0017.cpp)                                       |
 |  0019  |   Medium   | [Remove Nth Node From the End of List](Problems/0019.cpp)                                        |
 |  0020  |    Easy    | [Valid Parentheses](Problems/0020.cpp)                                                           |
 |  0021  |    Easy    | [Merge Two Sorted Lists](Problems/0021.cpp)                                                      |
@@ -75,6 +77,7 @@ for solving problems.
 |  0075  |   Medium   | [Sort Colors](Problems/0075.cpp)                                                                 |
 |  0077  |   Medium   | [Combinations](Problems/0077.cpp)                                                                |
 |  0078  |   Medium   | [Subsets](Problems/0078.cpp)                                                                     |
+|  0079  |   Medium   | [Word Search](Problems/0079.cpp)                                                                 |
 |  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)                                              |
diff --git a/Templates/bfs_floodfill_recursive.cpp b/Templates/bfs_floodfill_recursive.cpp
@@ -0,0 +1,27 @@
+// Matrix BFS/Flood fill Recursive
+
+typedef vector<vector<int>> Matrix;
+typedef vector<vector<bool>> Marked;
+const vector<pair<int, int>> offsets = {
+    { 0,  1},
+    { 0, -1},
+    { 1,  0},
+    {-1,  0}
+};
+
+int n, m;
+int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
+
+bool dfs(const Matrix &mat, Marked &mark, int a, int b) {
+  if (got == word.size()) return true;
+
+  mark[a][b] = true;
+  for (auto [oa, ob] : offsets) {
+    int x = a + oa, y = b + ob;
+    if (!valid(x, y) || mark[x][y]) continue;
+    if (dfs(mat, mark, x, y)) return true;
+  }
+  mark[a][b] = false;
+
+  return false;
+}