Hash

720. Longest Word in Dictionary

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.
Example 1:
Input:
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation:
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

看到前缀，想到trie，有的时候不需要实现trie，用hash也行。每进来一个单词，将26个字母试着加到后面，看看在不在hash里。用BFS找最长的。String compareTo的用法。

class Solution {
    public String longestWord(String[] words) {
        Set<String> set = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        for (String word : words) {
            set.add(word);
            // push words that length is 1 to queue 
            if (word.length() == 1) {
                queue.add(word);
            }
        }
        // bfs
        String res = "";
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            res = min(res, cur);
            // from a to z, append it to cur to check if the new String is in set
            for (char c = 'a'; c <= 'z'; c++) {
                if (set.contains(cur + c)) {
                    queue.add(cur + c);
                }
            }
        }
        
        return res;
    }
    
    private String min(String s1, String s2) {
        if (s1.length() < s2.length()) {
            return s2;
        } else if (s1.length() > s2.length()) {
            return s1;
        } else {
            return s1.compareTo(s2) < 0 ? s1 : s2;
        }
    }
}

如何设计Hash的key和value

41. First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Hash的方法应该首先想到，如果O1的额外空间想到用swap，利用index和值的关系做。

    public int firstMissingPositive(int[] A) {
        int i = 0;
        while(i < A.length){
            if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++;
            else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);
            else i++;
        }
        i = 0;
        while(i < A.length && A[i] == i+1) i++;
        return i+1;
    }
    
    private void swap(int[] A, int i, int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

387. First Unique Character in a String

One pass解决
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

    public int firstUniqChar(String s) {
        // store the first index (1-base) of each character
        // if the char appear more than once, record -1
        int[] memo = new int[26];
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (memo[c - 'a'] == 0) {
                memo[c - 'a'] = i + 1;
            } else if (memo[c - 'a'] > 0){
                memo[c - 'a'] = -1;
            } else {
                // keep -1
            }
        }
        // index+1 / -1 / 0
        int min = Integer.MAX_VALUE;
        for (int i : memo) {
            if (i > 0) {
                min = Math.min(min, i);
            }
        }
        if (min == Integer.MAX_VALUE) {
            return -1;
        }
        return min - 1;
    }

676. Implement Magic Dictionary

Implement a magic directory with buildDict, and search methods.
For the method buildDict, you'll be given a list of non-repetitive words to build a dictionary.
For the method search, you'll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.
Example 1:
Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False

设计的数据结构要求string改一个字符能变成相等的，不能不改，不能添加。
key value的设计是关键。比如hello， hallo，Map的key是h*llo，value是一个list，存被替过的字符。注意的一点是在这种情况下，hallo是要返回true的，算个corner case吧。

class MagicDictionary {

    /** Initialize your data structure here. */
    Map<String, Set<Character>> map;
    public MagicDictionary() {
        map = new HashMap<>();
    }
    
    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        for (String word : dict) {
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                String newWord = word.substring(0, i) + '*' + word.substring(i + 1);
                if (!map.containsKey(newWord)) {
                    map.put(newWord, new HashSet<Character>());
                }
                map.get(newWord).add(c);
            }
        }
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    public boolean search(String word) {
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            String newWord = word.substring(0, i) + '*' + word.substring(i + 1);

            if (map.containsKey(newWord)) {
                    if (!map.get(newWord).contains(c) || (map.get(newWord).contains(c) && map.get(newWord).size() > 1)) {
                        return true;
                    }
                }
            }
            return false;
    }
}

748. Shortest Completing Word

Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
Output: "steps"
Explanation: The smallest length word that contains the letters "S", "P", "S", and "T".
Note that the answer is not "step", because the letter "s" must occur in the word twice.
Also note that we ignored case for the purposes of comparing whether a letter exists in the word.

1. toLowercase()
   2. Character.isLetter('a')
   3. use char array rather than hash

380. Insert Delete GetRandom O(1)

设计一个数据结构支持O(1)的插入删除返回随机数

hash支持O1的insert和delete但无法返回随机数，list可以通过index支持O1的删除和插入
所以用hashmap保存value-index信息，同时也维护一个arraylist
答案只删除array list的最后位置，如果不是要swap

public class RandomizedSet {
    ArrayList<Integer> nums;
    HashMap<Integer, Integer> locs;
    Random rand = new Random();
    /** Initialize your data structure here. */
    public RandomizedSet() {
        nums = new ArrayList<Integer>();
        locs = new HashMap<Integer, Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        boolean contain = locs.containsKey(val);
        if ( contain ) return false;
        locs.put( val, nums.size());
        nums.add(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        boolean contain = locs.containsKey(val);
        if ( ! contain ) return false;
        int loc = locs.get(val);
        if (loc < nums.size() - 1 ) { // not the last one than swap the last one with this val
            int lastone = nums.get(nums.size() - 1 );
            nums.set( loc , lastone );
            locs.put(lastone, loc);
        }
        locs.remove(val);
        nums.remove(nums.size() - 1);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        return nums.get( rand.nextInt(nums.size()) );
    }
}