刷题记录

Problem: You have a list of  words  and a  pattern , and you want to know which words in  words  matches the pattern. A word matches the pattern if there exists a permutation of letters  p  so that after replacing every letter  x  in the pattern with  p(x) , we get the desired word. ( Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter. ) Return a list of the words in  words  that match the given pattern.  You may return the answer in any order. Example 1: Input: words = ["abc","deq","mee","aqq","dkd","ccc"] , pattern = "abb" Output: ["mee","aqq"] Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. "ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation, since a and b map to t...

Problem: Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"] , Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lowercase. The order of your output does not matter. Analysis: What's in common of anagrams is they are the same if we sort them. So use a map, key is the sorted string, value is the anagram list.  Solution: class Solution { public List< List< String > > groupAnagrams ( String [] strs) { List< List< String > > res = new ArrayList<> (); if (strs == null || strs . length == 0 ) return res; Map< String , List< String > > map = new HashMap<> (); for ( int i = 0 ; i < strs . length; i ++ ) { char [] ch...

Problem: Given a binary tree, return the  vertical order  traversal of its nodes' values. (ie, from top to bottom, column by column). If two nodes are in the same row and column, the order should be from  left to right . Examples: Given binary tree  [3,9,20,null,null,15,7] , 3 /\ / \ 9 20 /\ / \ 15 7 return its vertical order traversal as: [ [9], [3,15], [20], [7] ] Given binary tree  [3,9,8,4,0,1,7] , 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 return its vertical order traversal as: [ [4], [9], [3,0,1], [8], [7] ] Given binary tree  [3,9,8,4,0,1,7,null,null,null,2,5]  (0's right child is 2 and 1's left child is 5), 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 /\ / \ 5 2 return its vertical order traversal as: [ [4], [9,5], [3,0,1], [8,2], [7] ] 7/5/2018 update: To further optimize the solution. Use another queue to keep trac...

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: This is a  follow up  of  Shortest Word Distance . The only difference is now you are given the list of words and your method will be called  repeatedly  many times with different parameters. How would you optimize it? Design a class which receives a list of words in the constructor, and implements a method that takes two words  word1  and  word2  and return the shortest distance between these two words in the list. For example, Assume that words =  ["practice", "makes", "perfect", "coding", "makes"] . Given  word1  =  “coding” ,  word2  =  “practice” , return 3. Given  word1  =  "makes" ,  word2  =  "coding" , return 1. Analysis: pre process array, store each words occurrence index to hashtable. Then compare distance of two words' indexes. Suppose we have word1 with indexes [2,5,8,9], word2 with indexes [4,7,11]. We can compare the starting indexces fir...

Problem: Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user's news feed. Your design should support the following methods: postTweet(userId, tweetId) : Compose a new tweet. getNewsFeed(userId) : Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. follow(followerId, followeeId) : Follower follows a followee. unfollow(followerId, followeeId) : Follower unfollows a followee. Example: Twitter twitter = new Twitter(); // User 1 posts a new tweet (id = 5). twitter.postTweet(1, 5); // User 1's news feed should return a list with 1 tweet id -> [5]. twitter.getNewsFeed(1); // User 1 follows user 2. twitter.follow(1, 2); // User 2 posts a new tweet (id = 6). twitter.postTweet(2, 6); // User 1's...

Problem: An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations: a) it --> it (no abbreviation) 1 b) d|o|g --> d1g 1 1 1 1---5----0----5--8 c) i|nternationalizatio|n --> i18n 1 1---5----0 d) l|ocalizatio|n --> l10n Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no  other  word from the dictionary has the same abbreviation. Example:  Given dictionary = [ "deer", "door", "cake", "card" ] isUnique("dear") -> false isUnique("cart") -> true isUnique("cane") -> false isUnique("make") -> true Analysis: The abbreviation has just one form, starting char + number of chars between + ending char. T...

Problem: Given two strings  s  and  t , determine if they are isomorphic. Two strings are isomorphic if the characters in  s  can be replaced to get  t . All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself. For example, Given  "egg" ,  "add" , return true. Given  "foo" ,  "bar" , return false. Given  "paper" ,  "title" , return true. Analysis: Identical problem to word pattern.  Solution: class Solution { public boolean isIsomorphic ( String s, String t) { Map< Character , Character > map = new HashMap<> (); for ( int i = 0 ; i < strs . length; i ++ ) { char c1 = s . charAt(i); char c2 = t . charAt(i); String word = strs[i]; if (map . containsKey(c1) &...

Problem: Given a  pattern  and a string  str , find if  str  follows the same pattern. Here  follow  means a full match, such that there is a bijection between a letter in  pattern  and a  non-empty  word in  str . Examples: pattern =  "abba" , str =  "dog cat cat dog"  should return true. pattern =  "abba" , str =  "dog cat cat fish"  should return false. pattern =  "aaaa" , str =  "dog cat cat dog"  should return false. pattern =  "abba" , str =  "dog dog dog dog"  should return false. Notes: You may assume  pattern  contains only lowercase letters, and  str  contains lowercase letters separated by a single space. Analysis: The difficulty of this problem lies in that how to decide new word in new pattern character not exist before. "abba" "dog cat cat dog". If there is a new pattern char, we need to make sure its paired...

Problem: The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer  n  representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given  n  = 2, return  [0,1,3,2] . Its gray code sequence is: 00 - 0 01 - 1 11 - 3 10 - 2 Note: For a given  n , a gray code sequence is not uniquely defined. For example,  [0,2,3,1]  is also a valid gray code sequence according to the above definition. For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that. Analysis: We can conclude from the above image that, n can get from  n - 1. n == 1, code is 0, 1. Add 0 to front we have 00, 01. Then add 1 to front and reverse the code, we get 11, 10. Thus we have n == 2's code: 00, 01, 11, 10. Solution: class Solution { public List< Integer > grayCode ( i...

Problem: All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. For example, Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT", Return: ["AAAAACCCCC", "CCCCCAAAAA"]. Analysis: 用bit manipulation 太难了，想不出来。 Use two sets, one stores distinct string, the other stores repeated. Solution: class Solution { public List< String > findRepeatedDnaSequences ( String s) { List< String > res = new ArrayList<> (); Set< String > seen = new HashSet<> (); Set< String > repeated = new HashSet<> (); if (s == null || s . length() == 0 ) return res; for ( int i = 0 ; i <= s . length() - 10 ; i ++ )...