Posts

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. ...

The problem A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise. Examples Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true] Explanation Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True Constraints 1 <= word.length, prefix.length <= 2000 word and prefix consist only of lowercase English letters. At most 3 * 10⁴ calls in total will be made to insert, search, and startsWith. Prefix Tree Array solution final class TrieNode { var children: [TrieNode?] var endOfWord: Bool init() { self.children = Array(repeating: nil, count: 26) self.endOfWord = false } } class Trie { private let root: TrieNode private let aAsciiValue: Int = Int(Character("a").asciiValue!) init() { self.root = TrieNode() } func insert(_ word: String) { var curr = self.root for c in word { let i = Int(c.asciiValue!) - aAsciiValue if curr.children[i] == nil { curr.children[i] = TrieNode() } curr = curr.children[i]! } curr.endOfWord = true } func search(_ word: String) -> Bool { var curr = self.root for c in word { let i = Int(c.asciiValue!) - aAsciiValue if curr.children[i] == nil { return false } curr = curr.children[i]! } return curr.endOfWord } func startsWith(_ prefix: String) -> Bool { var curr = self.root for c in prefix { let i = Int(c.asciiValue!) - aAsciiValue if curr.children[i] == nil { return false } curr = curr.children[i]! } return true } } Explanation Before we start implementing Trie, let’s take a look at what we are going to do. ...

The Problem Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can 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. Examples Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true ...