The problem There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges. The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c). ...

The Problem Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors: class Node { public int val; public List<Node> neighbors; } Test Case Format For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node has val == 1, the second node has val == 2, and so on. The graph is represented in the test case using an adjacency list. ...

The Problem Given an m x n 2D binary grid grid, which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water. Examples Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3 Constraints m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] is '0' or '1'. Depth-First Search Solution func numIslands(_ grid: [[Character]]) -> Int { var grid = grid let ROWS = grid.count let COLS = grid[0].count let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] var islands = 0 func dfs(_ r: Int, _ c: Int) { if (r < 0 || c < 0 || r >= ROWS || c >= COLS || grid[r][c] == "0" ) { return } grid[r][c] = "0" for direction in directions { let dr = direction[0] let dc = direction[1] dfs(r + dr, c + dc) } } for r in 0 ..< ROWS { for c in 0 ..< COLS { if grid[r][c] == "1" { dfs(r, c) islands += 1 } } } return islands } Explanation From the description of the problem, we can see that we have islands formed by connecting adjacent land horizontally or vertically. If we draw a visual representation, we can find islands that are connected vertically or horizontally and surrounded by water. ...

The Problem Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. Examples Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] Output: ["eat","oath"] ...

The problem Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: WordDictionary() Initializes the object. void addWord(word) Adds word to the data structure; it can be matched later. bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots ('.'), where dots can be matched with any letter. Examples Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true] Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True Constraints 1 <= word.length <= 25 word in addWord consists of lowercase English letters. word in search consists of '.' or lowercase English letters. There will be at most 2 dots in word for search queries. At most 10^4 calls will be made to addWord and search. Brute force solution class WordDictionary { private var store: [String] init() { self.store = [] } func addWord(_ word: String) { self.store.append(word) } func search(_ word: String) -> Bool { let wordArray = Array(word) let wordCount = wordArray.count for w in self.store { let wArray = Array(w) let wCount = wArray.count if wCount != wordCount { continue } var i = 0 while i < wCount { if wArray[i] == wordArray[i] || wordArray[i] == "." { i += 1 } else { break } if i == wCount { return true } } } return false } } Explanation We can solve this problem in a brute-force way by using an array. It is not the most efficient solution because the search operation will take O(m * n) time. We can optimize it by using a Trie (Prefix Tree) data structure. ...