Swift

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

The Problem Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. The frequency of an element x is the number of times it occurs in the array. ...

The Problem The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. For example, for arr = [2,3,4], the median is 3. For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5. Implement the MedianFinder class: MedianFinder() initializes the MedianFinder object. void addNum(int num) adds the integer num from the data stream to the data structure. double findMedian() returns the median of all elements so far. Answers within 10⁻⁵ of the actual answer will be accepted. Examples Input ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Output [null, null, null, 1.5, null, 2.0] Explanation MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2) medianFinder.addNum(3); // arr = [1, 2, 3] medianFinder.findMedian(); // return 2.0 Constraints -10⁵ <= num <= 10⁵ There will be at least one element in the data structure before calling findMedian(). At most 5 * 10⁴ calls will be made to addNum and findMedian(). Follow-up: If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution? If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution? Sorting Solution class MedianFinder { private var data: [Int] init() { self.data = [] } func addNum(_ num: Int) { data.append(num) } func findMedian() -> Double { data.sort() let n = data.count if (n & 1) != 0 { return Double(data[n / 2]) } else { return (Double(data[n / 2]) + Double(data[n / 2 - 1])) / 2 } } } Explanation One approach to solving this problem is to apply a built-in sorting algorithm. To find the result, we use an array to collect all numbers added using the addNum method. ...