228. Summary Ranges

Your input

[0,1,2,4,5,7]

Your answer

["0->1->2","4->5"]

Expected answer

["0->2","4->5","7"]

Input:[0,2,3,4,6,8,9]

Output:["0->0","2->4","6->6","8"]

Expected:["0","2->4","6","8->9"]

50.15 %

// LC228 Beats 50.15 %
// There are 2 edge cases:
// 1.start == end like "6->6" should be treated as a single number "6"， so we should check prev != start
// 2. Since discontinuous gap triggers adding String to result, the last String won't be added. We should deal with it before return
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if (nums == null || nums.length <= 0) return result;
        int prev = nums[0];
        int start = prev;
        StringBuilder sb = new StringBuilder();
        sb.append(start);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != prev + 1) {
                if (start != prev) sb.append("->" + prev);
                result.add(sb.toString()); // add previous String to result
                sb.setLength(0); // clear StringBuilder
                start = nums[i];
                sb.append(start); // new Starting point
            }
            prev = nums[i];
        }
        if (sb.length() != 0) {
            if (start != prev) sb.append("->" + prev);
            result.add(sb.toString());
        }
        return result;
    }
}

720. Longest Word in Dictionary

Version #1 Trie + DFS
因为只有length 比当前的max大才会Update，所以保证了当有不只一个max的时候，返回的是 smallest lexicographical order

91.21 %
// Time O(n*l) Space O(n*l) -> n:possible words count, l:average word length
class Solution {
    class TrieNode {
    TrieNode[] children;
    boolean isWord;
    public TrieNode() {
        children = new TrieNode[26];
    }
}
class Trie {
    TrieNode root;
    public Trie(String[] words) {
        root = new TrieNode();
        for (String word : words) {
            this.insert(word);
        }
    }
    public void insert(String word) {
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (curr.children[index] == null) {
                curr.children[index] = new TrieNode();
            }
            curr = curr.children[index];
        }
        curr.isWord = true;
    }
}
    public String longestWord(String[] words) {
        if (words == null || words.length == 0) return "";
        Trie trie = new Trie(words);
        String[] result = new String[]{""};
        dfs(trie.root, result, new StringBuilder());
        return result[0];
    }
    private void dfs(TrieNode currNode, String[] result, StringBuilder sb) {
        TrieNode[] children = currNode.children;
        boolean flag = false;
        for (int i = 0; i < children.length; i++) {
            if (children[i] != null && children[i].isWord) {
                flag = true;
                sb.append((char)('a' + i));
                dfs(children[i], result, sb);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        if (!flag && sb.length() > result[0].length()) {
            result[0] = sb.toString();
        }
    }
 
}

Version #2 HashSet

二刷
class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> set = new HashSet<>();
        String result = "";
        for (String word : words) {
            if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
                set.add(word);
                if (word.length() > result.length()) {
                    result = word;
                }
            }
        }
        return result;
    }
}

一刷
 60.70 % 
// Time O(nlogn) Space O(n*l)
class Solution {
    public String longestWord(String[] words) {
        if (words == null || words.length == 0) return "";
        Arrays.sort(words);
        Set<String> dict = new HashSet<>();
        String result = "";
        for (String word : words) {
            if (word.length() == 1 || dict.contains(word.substring(0, word.length() - 1))) {
                dict.add(word);
                if (word.length() > result.length()) result = word;
            }
        }
        return result;
    }
}

698. Partition to K Equal Sum Subsets

Version #1 DFS

89.41 % 

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (nums == null || k <= 0 || nums.length < k) return false;
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % k != 0) return false;
        int target = sum / k;
        Arrays.sort(nums); // Must sort and add from larger elements
        boolean[] visited = new boolean[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            if (!visited[i] && !partition(nums, i, visited, target)) return false;
        }
        return true;
    }
    public boolean partition(int[] nums, int start, boolean[] visited, int target) {
        if (nums[start] > target) return false;
        // nums[start] <= target
        visited[start] = true;
        if (nums[start] == target) {
            return true; // no need to reset, marked as visited
        }
        for (int i = start - 1; i >= 0; i--) {
            if (visited[i]) continue; // make sure nums[i] is not visited
            if (partition(nums, i, visited, target - nums[start])) return true;
        }
        visited[start] = false;
        return false;
    }
}

692. Top K Frequent Words

Version #1 Sort All with Lambda
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> wordCount = new HashMap<>();
        Integer tempCount = null;
        List<String> distinctWords = new ArrayList<>();
        // O(n) Space + O(n) Time to get Count
        for (String word : words) {
            tempCount = wordCount.get(word);
            if (tempCount == null) {
                wordCount.put(word, 1);
                distinctWords.add(word);
            } else {
                wordCount.put(word, tempCount + 1);
            }
            tempCount = null;
        }
        Collections.sort(distinctWords, (s1, s2) -> {
            if (wordCount.get(s1) == wordCount.get(s2)){
                return s1.compareTo(s2);
            } else {
                return wordCount.get(s2).compareTo(wordCount.get(s1));
            }
        });
        return distinctWords.subList(0, k);
    }
}