LeetCode(108) -- 211, 213

P211. Add and Search Word - Data structure design (Medium)

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.

Solution

class WordDictionary {
    private Trie root;

    public WordDictionary() {
        root = new Trie();
    }

    public void addWord(String word) {
        Trie curr = root;
        char[] chars = word.toCharArray();
        for (char c : chars) {
            if (curr.children[c - 'a'] == null) {
                curr.children[c - 'a'] = new Trie();
            }
            curr = curr.children[c - 'a'];
        }
        curr.isWord = true;
    }

    public boolean search(String word) {
        return dfs(word.toCharArray(), 0, root);
    }

    private boolean dfs(char[] chars, int i, Trie node) {
        if (i == chars.length()) {
            return node.isWord;
        }
        if (char[i] == '.') {
            for (int j = 0; j < 26; j++) {
                if (node.children[j] != null && dfs(chars, i + 1, node.children[j])) {
                    return true;
                }
            }
        } else {
            return node.children[chars[i] - 'a'] != null && dfs(chars, i + 1, node.children[chars[i] - 'a']);
        }
        return false;
    }

    static class Trie {
        public Trie[] children = new Trie[26];
        public boolean isWord;
    }
}

The Best Solution

class WordDictionary {
    private TrieNode root;
    
    /** Initialize your data structure here. */
    public WordDictionary() {
        //add dummy
        this.root = new TrieNode('\0');
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode cur = root;
        char[]charArray = word.toCharArray();
        for(char c : charArray){
            if(cur.children[c - 'a'] == null){
                // create a new TrieNode and insert into trie
                // TrieNode newTrieNode = new TrieNode(c - 'a');            
                // cur[c - 'a'] = newTrieNode;
                cur.children[c - 'a'] = new TrieNode(c);   
            }
            cur = cur.children[c - 'a'];
        }
        cur.isWord = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        char[] charArray = word.toCharArray();
        return dfs(root, charArray, 0);
        
    }
    private boolean dfs(TrieNode cur, char[]charArray, int index){
        if(cur == null) return false;
        if(index == charArray.length)   return cur.isWord;
      
        char curChar = charArray[index];
        if(curChar == '.'){
            for(TrieNode next : cur.children){
                if(dfs(next, charArray, index + 1))  return true;
            }
            return false;
        }
         return dfs(cur.children[curChar - 'a'], charArray, index + 1);
    }
}
class TrieNode{
    public char character;
    public TrieNode[]children;   
    public boolean isWord;
    
    public TrieNode(char val){
        character = val;
        children = new TrieNode[26];
        isWord = false;
    }
}
/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

逻辑似乎是完全一样的，但是不知道为什么最快。

P213. House Robber II (Medium)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }
    
    private int rob(int[] num, int lo, int hi) {
        int include = 0, exclude = 0;
        for (int j = lo; j <= hi; j++) {
            int i = include, e = exclude;
            include = e + num[j];
            exclude = Math.max(e, i);
        }
        return Math.max(include, exclude);
    }
}

P215. Kth Largest Element in an Array (Medium)

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

My Solution

public class P215 {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        int j = nums.length;
        for (int i = 0; i < k; i++) {
            j--;
        }
        return nums[j];
    }
}

80%

Solution

import java.util.Random;

class Solution {
    int[] nums;

    
}