-
LeetCode 648: Replace Words
link Sort and search If we sort the dictionary, the first root that is a prefix of a word should be used to replace that word. To make the search efficient, we can binary-search the insert position of word[0] in the sorted dictionary and thereon we do linear-search. Say , the longest root has length…
-
LeetCode 1268: Search Suggestions System
link The question is a bit misleading. From the description, it feels like the lexicographical sorting should be applicable only if there are more than three products, which is not the case. As long as there are more than one suggestions, we must emit them in lexicographic order capping at three suggestions. Sort and search…
-
LeetCode 208: Implement Trie (Prefix Tree)
link We represent the Trie as a tree with TrieNode‘s. An edge has two end points and a label: . Following an edge, , consumes the word character, . If a node is reached consuming the last character of a word, that node is marked with end_of_word = True. The root is a special node,…
-
LeetCode 653: Two Sum IV – Input is a BST
link Recursive With an inorder traversal, we can sort the values in linear time. Then, we can use two pointers approach to search for the pair, again in linear time. Time: , space: . Keeping track of already seen values, we can search the pair while we are traversing the tree. Iterative BFS + seen…
-
LeetCode 127: Word Ladder
link Unidirectional BFS The problem is to find the shortest path in an undirected word graph from beginWord to endWord. An edge means: is a word in wordList and Hamming distance between the words and is 1. We use BFS. Say and are the vertex and edge sets of the word graph. Here, . If…
-
LeetCode 101: Symmetric Tree
link Iterative For the tree to be symmetric, each level (including missing children) must be a palindrome. With a single BFS we process an entire level per iteration and check if the level is a palindrome. Time: , space: . Recursive For a subtree rooted at a node, although we cannot define symmetry in terms…
-
LeetCode 987: Vertical Order Traversal of a Binary Tree
link Recursive Each node has three coordinates: row, col, val. The problem is to sort the node-values by its coordinates: column id, row id and value. We emit column values in sorted order: start with lowest column id and go towards highest. Tracking column id is easy: if has col, its left child has (col-1)…
-
LeetCode 116: Populating Next Right Pointers in Each Node
link In each iteration of BFS we can process the entire level, linking the nodes with next pointer. Time: , space: . Follow-up: Use only constant extra space. Since the implicit stack of recursion is not counted as extra space, we can connect siblings. The right child should point to the left cousin.
-
LeetCode 103: Binary Tree Zigzag Level Order Traversal
link In each iteration of BFS, we process entire level. For odd levels, order is reversed. Time: , space: .
-
LeetCode 102: Binary Tree Level Order Traversal
link In each iteration of BFS, we process the entire level. Time: , space: .
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
unreasonably effective 