Hashmap

10 flashcards · Other · by Steven Bui

1. 290. Word Pattern You have a String pattern, which is a string of random characters, and a String s, which is a string of words separated by spaces. Return true if each character in pattern maps to a word in s in the same order. There must be a 1:1 relationship, so a character cannot map to two words, and vice versa. ex. Input: pattern: "abba" s: "cat dog dog cat" Output: true ---------------------------------------------------------------------------------- public boolean method (String patter…

   Approach: First, use a split() method on the s string to break it up into an array. Return false if the number of elements in s is different from the length of pattern. Then, create 2 maps: one mapping characters of pattern to words in the s array, and vice versa. In a for-loop, save both the character from pattern and the word from the s array. If the character is in the corresponding map already, then it should map to the word in the s array. If it does not exist, add it. Do the same for the…

2. 1. Two Sum Given an int array nums and a number target, return the indices of 2 numbers in nums that add up to target. ex. Input: num = [3, 2, 4], and target = 6 Output: [1, 2] ---------------------------------------------------------------------------------- public int[] method (int[] nums, int target) { .... }

   Approach: Create a hash map with the key = number at the index, and value = index. Then, iterate the array and for each number, check if target - number is in the hash map already. If so, return the current index and the hash map's value. Code: public int[] method (int[] nums, int target) { ....HashMap<Integer, Integer> map = new HashMap<>(); ....for (int i = 0; i < nums.length; i++) { ........if (map.containsKey(target - nums[i]) { ............return new int[] { maps.get(target - nums[i]), i }…

3. 242. Valid Anagram Given 2 strings s and t, return true if s and t are anagrams of each other. The strings can contain any characters. ex. Input: s = "rat", and t = "tar" Output: true ---------------------------------------------------------------------------------- public boolean method (String s, String t) { .... }

   Approach: First, check if the 2 strings are the same length or not. Then, create a hash map with the key = character of the string, and val = count of each character. Turn s to a char array and add each character to the map. Then, turn t to a char array, checking first that the character is in the map, and if it is, decrement the count. If the count decrements to 0, remove it from the map. Return true if the map is empty. Code: public boolean method (String s, String t) { ....if (s.length() !=…

4. 205. Isomorphic Strings Given 2 strings s and t, return true if the characters in s can be replaced 1:1 to create t. No 2 characters can map to the same character. ex. Input: s = "egg", and t = "add" Output: true ---------------------------------------------------------------------------------- public boolean method (String s, String t) { .... }

   Approach: First, check that s and t are the same length. Then, create 2 maps: one mapping characters of s to t, and vice versa. In a for-loop, save both characters at the corresponding index. If the character in s is in the corresponding map already, then it should map to the character in t. If it does not exist, add it. Do the same for the opposite map. Code: public boolean method (String s, String t) { ....if (s.length() != t.length()) { ........return false; ....} ....HashMap<Character, Stri…

5. 2215. Difference Between 2 Arrays Given 2 int arrays nums1 and nums2, return an ArrayList of size 2, where list.get(0) is an ArrayList containing the elements in nums1 that are not in nums2, and list.get(1) is an ArrayList containing the elements in nums2 that are not in nums1. ex. Input: nums1 = [1, 2, 3], and nums2 = [2, 4, 6] Output: [ [1, 3], [4, 6] ] ---------------------------------------------------------------------------------- public List<List<Integer>> method (int[] nums1, int[] nums…

   Approach: Create 2 hash sets. Add all of the contents of the arrays into the corresponding sets. Then, create 2 array lists. Go through the numbers in each set, and if the other set does not contain that number, add it to the list. Make a new array list of array lists, and add those 2 array lists to it. Code: public List<List<Integer>> method (int[] nums1, int[] nums2) { ....Set<Integer> set1 = new HashSet<>(); ....Set<Integer> set2 = new HashSet<>(); ....for (int i : nums1) { ........set1.add(…

6. 202. Happy Number Given a number n, return true if for each of the digits in the number (ex. 100 is 1, 0, 0), when you square each digit, you can add them all together to get either 1 or another number that can repeat this process to get to 1. ex. Input: n = 19 Output: true 12 + 02 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1 ---------------------------------------------------------------------------------- public boolean method (int n) { .... }

   Approach: First, create a helper method that takes n and returns what the next number would be. In your main method, have a slow pointer that checks the next number 1 at a time, and a fast pointer that checks the next number 2 at a time. Make the slow pointer call the helper method once and the fast pointer call the helper method twice. While fast != 1, move slow forward 1 and fast forward 2. Since the while-loop is while slow != 1, make a check to return false if slow == fast (since this means…

7. 1207. Unique Number of Occurrences Given an int array arr, return true if the each number in the array shows up a unique number of times. In other words, 2 numbers do not show up the same number of times. ex. Input: array = [1, 1, 1, 2, 2, 3] Output: true (1 shows up 3 times, 2 shows up 2 times, etc.) ---------------------------------------------------------------------------------- public boolean method (int[] arr) { .... }

   Approach: First, use a hash map to put each number from the array into the map, where the key is the number itself and the value is how many times it occurs. Then, use a hash set to go through the values() of the map (returning a Collection<>). Use the hash set's add() method to try adding the number to the set, where it returns false if the number cannot be added to the set. Code: public boolean method (int[] arr) { ....HashMap<Integer, Integer> map = new ....HashMap<>(); ....for (int i : arr)…

8. 49. Group the Anagrams Together Given a String array strs, group the anagrams together into an ArrayList, and return an ArrayList of those ArrayLists. ex. Input: strs = ["eat", "ate", "tan", "nat", "bat"] Output" [ ["eat", "ate"], ["tan", "nat"], ["bat"] ] ---------------------------------------------------------------------------------- public List<List<String>> method (String[] strs) { .... }

   Approach: First, create a new HashMap, where the key is the string in sorted alphabetical order, and the value is an ArrayList of Strings that are also anagrams of that key. In a for-each loop for each string in strs, convert the string into a char array, sort it, and turn it back into a string (now in sorted alphabetical order). Check if this sorted word is in the map yet. If not, add it to the map with an empty ArrayList. Then, get the list of anagrams for that string using the map, and add t…

9. 217. Contains Duplicate Given an int array nums, return true if any number appears more than once. ex. Input: nums = [1, 2, 3, 1] Output: true ---------------------------------------------------------------------------------- public boolean method (int[] nums) { .... }

   Approach: Create a new HashMap with key = the number, and value = anything. If the key already exists in the map, return true. If not, add it. Code: public boolean method (int[] nums) { ....HashMap<Integer, Boolean> map = new HashMap<>(); ....for (int i : nums) { ........if (map.containsKey(i)) ............return true; ........map.put(i, false); ....} ....return false; } Time complexity: O(n) if you go through every entry in nums. Space complexity: O(n) if there are no duplicates and you store…

10. 219. Contains Duplicate II Given an int array nums, return true if a number appears more than once AND if those two numbers are at most k spaces away from each other. ex. Input: nums = [1, 2, 3, 1], and k = 3 Output: true (Because the number '1' is at indices 0 and 3). ---------------------------------------------------------------------------------- public boolean method (int[] nums, int k) { .... }

    Approach: Create a new HashMap with key=the number itself, and value=the index. If the key already exists in the map, return true if its value is at most k spaces away from the current index. If not, add it. Code: public boolean method (int[] nums, int k) { ....HashMap<Integer, Integer> map = new HashMap<>(); ....for (int i = 0; i < nums.length; i++) { ........if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) ............return true; ........map.put(nums[i], i); ....} ....return false;…