刷题记录

Problem: Given a list of words, we may encode it by writing a reference string  S  and a list of indexes  A . For example, if the list of words is  ["time", "me", "bell"] , we can write it as  S = "time#bell#"  and  indexes = [0, 2, 5] . Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character. What is the length of the shortest reference string S possible that encodes the given words? Example: Input: words = ["time", "me", "bell"] Output: 10 Explanation: S = "time#bell#" and indexes = [0, 2, 5 ]. Analysis: 核心思想是合并suffix一样的单词。比如time和me，suffix是一个的，可以把me去掉。可以用2种方法做。 Approach 1: Hash set 先把所有的word加入到一个set里面。然后遍历所有word。 对于每一个word，从index 1开始拆分suffix, 看这个word的suffix在不在set里面。如果在则从set里面删除。 class Solution { public int minimumLengthEncoding ( String [] words) { Set< String > set = new HashS...

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

Problem: Implement a MapSum class with  insert , and  sum  methods. For the method  insert , you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one. For the method  sum , you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix. Example 1: Input: insert("apple", 3), Output: Null Input: sum("ap"), Output: 3 Input: insert("app", 2), Output: Null Input: sum("ap"), Output: 5 Analysis: Solution 1 DFS: 这道题trie的方法是我自己想出来的。store val to TrieNode, from prefix use DFS go down and sum up. Leetcode discussion 里面谷歌大神的实现太牛逼了，原来DFS还可以这样玩。 class MapSum { class TrieNode { TrieNode [] children = new TrieNode [ 26 ]; int val; } TrieNode root; /** Initialize your data struc...

Problem: In English, we have a concept called  root , which can be followed by some other words to form another longer word - let's call this word  successor . For example, the root  an , followed by  other , which can form another word  another . Now, given a dictionary consisting of many roots and a sentence. You need to replace all the  successor  in the sentence with the  root forming it. If a  successor  has many  roots  can form it, replace it with the root with the shortest length. You need to output the sentence after the replacement. Example 1: Input: dict = ["cat", "bat", "rat"] sentence = "the cattle was rattled by the battery" Output: "the cat was rat by the bat" Note: The input will only have lower-case letters. 1 <= dict words number <= 1000 1 <= sentence words number <= 1000 1 <= root length <= 100 1 <= sentence words length <= 1000 Analysis: 这道题是自己做出来的。 First...

Problem: 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"] . Analysis: 6/6/3028 update: 这道题的思想很简答，但是写成bug free各种情况都考虑到很难。这一遍保存word考虑到了，去重没想到。 ------------------- ------------------- ------------------- ------------------- ------------------- ------------------- ------------------- ------- 3/6/0218 update: The problem is how to validate the ...

Problem： 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 6/5/2018 update: 这次是自己想出来的如何处理‘.’。有.时候，需要遍历当前trienode所有的children。所以用递归比较好实现。 TrieNode的children用hashmap更方便。而且居然自己想出来如何处理，for循环里面boolean结果的方法，感觉快出山了。 class WordDictionary { class TrieNode { Map< Character , TrieNode > children; boolean isWord; public TrieNode () { children = new HashMap<> (); } } TrieNode root; /** Initialize your data structure here. */ public WordDictionary () { root = new Tri...

Problem: Implement a trie with  insert ,  search , and  startsWith  methods. 6/5/2018 update: 现在倾向于用hash map来表示children. class TrieNode { Map< Character , TrieNode > children; boolean isWord; public TrieNode () { children = new HashMap<> (); } } TrieNode root; /** Initialize your data structure here. */ public WordDictionary() { root = new TrieNode (); } /** Adds a word into the data structure. */ public void addWord( String word) { TrieNode cur = root; for ( char c : word . toCharArray()) { if ( ! cur . children . containsKey(c)) { cur . children . put(c, new TrieNode ()); } cur = cur . children . get(c); } cur . isWord = true; } -------- -------- -------- -------- -------- -------- -------- -------- -------- -------- -------- -------- -------- -----...