Posts

Showing posts with the label Trie

[LeetCode] 425. Word Squares

Given a set of words  (without duplicates) , find all  word squares  you can build from them. A sequence of words forms a valid word square if the  k th  row and column read the exact same string, where 0 ≤  k  < max(numRows, numColumns). For example, the word sequence  ["ball","area","lead","lady"]  forms a word square because each word reads the same both horizontally and vertically. b a l l a r e a l e a d l a d y Note: There are at least 1 and at most 1000 words. All words will have the exact same length. Word length is at least 1 and at most 5. Each word contains only lowercase English alphabet  a-z . Example 1: Input: ["area","lead","wall","lady","ball"] Output: [ [ "wall", "area", "lead", "lady" ], [ "ball", "area", "lead", "lady" ] ] Explanation: The ou...

[LeetCode] 642. Design Search Autocomplete System

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character  '#' ). For  each character  they type  except '#' , you need to return the  top 3  historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules: The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before. The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first). If less than 3 hot sentences exist, then just return as many as you can. When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list. Your job is to implement the following functions: The constructor function: AutocompleteSystem(String[] sent...

[LeetCode] 211. Add and Search Word - Data Structure Design

Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters  a-z  or  . . A  .  means it can represent any one letter. For example: addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true Note: You may assume that all words are consist of lowercase letters  a-z . click to show hint. You should be familiar with how a Trie works. If not, please work on this problem:  Implement Trie (Prefix Tree)  first. Thought process: Use trie. addWord: iterate through the word. Start from the root trie node. If current character does not map to a trie node, create a new one and map them. Otherwise, go to the next trie node. Search: iterate through the word. If current character is ...

[LeetCode] 336. Palindrome Pairs

Given a list of  unique  words, find all pairs of  distinct  indices  (i, j)  in the given list, so that the concatenation of the two words, i.e.  words[i] + words[j]  is a palindrome. Example 1: Given  words  =  ["bat", "tab", "cat"] Return  [[0, 1], [1, 0]] The palindromes are  ["battab", "tabbat"] Example 2: Given  words  =  ["abcd", "dcba", "lls", "s", "sssll"] Return  [[0, 1], [1, 0], [3, 2], [2, 4]] The palindromes are  ["dcbaabcd", "abcddcba", "slls", "llssssll"] Thought process: Put string -> index into a hash map. Iterate through every string. For each iteration, look at left = substring(0, i) and right = substring(i, string.length). If left is a palindrome, then if there is a string that's the reverse of right, we have a palindrome pair (map.get(reverse(right)), string). Similarly, if right is a palindrome, t...

[LeetCode] 212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. For example, Given  words  =  ["oath","pea","eat","rain"]  and  board  = [ [' o ',' a ','a','n'], ['e',' t ',' a ',' e '], ['i',' h ','k','r'], ['i','f','l','v'] ] Return  ["eat","oath"] . Note: You may assume that all inputs are consist of lowercase letters  a-z . click to show hint. You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier? If the current candidate does not exist in all words' prefix, you could stop bac...