LIKE CODING: May 2015

Tuesday, May 26, 2015

LeetCode [213] House Robber II

213. 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.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

//C++: 0ms alg1
class Solution {
public:
    int robL(vector<int> &num, int start) {
        int n = num.size();
        int dp[1000] = {0};        
        if(start==0){
            for(int i=2; i<=n; ++i){
                dp[i] = max(dp[i-2]+num[i-2], dp[i-1]);
            }
            return dp[n];
        }else{
            for(int i=3; i<=n+1; ++i){
                dp[i] = max(dp[i-2]+num[i-2], dp[i-1]);
            }
            return dp[n+1];            
        }
    }
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        return max(robL(nums, 0), robL(nums, 1));
    }
};

//C++: 0ms alg2 constant space
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;
        if(n==1) return nums[0];
        if(n==2) return max(nums[0], nums[1]);
        
        int p10 = nums[0], p20 = max(nums[0], nums[1]), pw0 = p20;//starting from 0
        int p11 = nums[1], p21 = max(nums[1], nums[2]), pw1 = p21;//starting from 1
        for(int i=2; i<n; ++i){
            if(i<n-1){//include nums[0], cannot include nums[n-1]
                pw0 = max(p10+nums[i], p20);
                p10 = p20;
                p20 = pw0;
            }
            if(i>2){//not include nums[0]
                pw1 = max(p11+nums[i], p21);
                p11 = p21;
                p21 = pw1;                
            }
        }
        return max(pw0, pw1);
    }
};

//Java
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==0) return 0;
        if(n==1) return nums[0];
        if(n==2) return Math.max(nums[0], nums[1]);
        
        return Math.max(helper(Arrays.copyOfRange(nums, 0, n-1)), helper(Arrays.copyOfRange(nums, 1, n)));
    }
    
    int helper(int[] nums){
        System.out.println(Arrays.toString(nums));
        int a = nums[0], b = Math.max(a, nums[1]);
        int i = 2;
        while(i<nums.length){
            int t = Math.max(a+nums[i++], b);
            a = b;
            b = t;
        }
        return b;
    }
}

LeetCode [212] Word Search II

212. Word Search II

Hard

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

class TrieNode{
public:
    char key;
    bool isTail = false;
    TrieNode* children[26] = {NULL};
    TrieNode(){}
    TrieNode(char k):key(k){}
};

class Trie{
public:
    TrieNode * root = new TrieNode();
    Trie(){}
    void insert(string word){
        TrieNode *p = root;
        for(char c:word){
            if(p->children[c-'a']==NULL){
                p->children[c-'a'] = new TrieNode(c);
            }
            p = p->children[c-'a'];
        }
        p->isTail = true;
    }
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie trie;
        for(string w:words) trie.insert(w);
        vector<string> ret;
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                dfs(i, j, m, n, board, trie.root, ret, "");
            }
        }
        return ret;
    }
   void dfs(int i, int j, int m, int n, vector<vector<char>>& board, TrieNode *t, vector<string> &ret, string cur){
            char c = board[i][j];
            board[i][j] = '#';
            if(c!='#' && t->children[c-'a']!=NULL){
                cur += c;
                if(t->children[c-'a']->isTail){
                    ret.push_back(cur);
                    t->children[c-'a']->isTail = false;
                }
                if(i-1>=0) dfs(i-1, j, m, n, board, t->children[c-'a'], ret, cur);
                if(i+1<m)  dfs(i+1, j, m, n, board, t->children[c-'a'], ret, cur);
                if(j-1>=0) dfs(i, j-1, m, n, board, t->children[c-'a'], ret, cur);
                if(j+1<n)  dfs(i, j+1, m, n, board, t->children[c-'a'], ret, cur);

            }
            board[i][j] = c;
    }

};

class Solution {
    int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    class Trie{
        boolean isEnd;
        Trie[] children = new Trie[26];
    }

    int m, n;
    Trie root;
    void insert(String w){
        Trie p = root;
        for(char c : w.toCharArray()){
            if(p.children[c-'a']==null){
                p.children[c-'a'] = new Trie();
            }
            p = p.children[c-'a'];
        }
        p.isEnd = true;
    }

    public List<String> findWords(char[][] board, String[] words) {
        m = board.length;
        n = board[0].length;
        root = new Trie();
        for(String w : words) insert(w);
        Set<String> set = new HashSet<>();
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                Trie p = root;
                char c = board[i][j];
                if(p.children[c-'a']!=null){
                    board[i][j] = '.';
                    String cur = ""+c;
                    search(i, j, board, set, p.children[c-'a'], cur);
                    board[i][j] = c;
                }
            }
        }

        List<String> list = new ArrayList<>(set);
        return list;
    }

    void search(int i, int j, char[][] board, Set<String> set, Trie p, String cur){
        if(p.isEnd) set.add(cur);
        for(int[] d : dirs){
            int ii = i+d[0], jj = j+d[1];
            if(ii>=0 && ii<m && jj>=0 && jj<n && board[ii][jj]!='.'){
                char c = board[ii][jj];
                if(p.children[c-'a']!=null){
                    board[ii][jj] = '.';
                    search(ii, jj, board, set, p.children[c-'a'], cur+c);
                    board[ii][jj] = c;
                }
            }
        }
    }
}

Friday, May 15, 2015

LeetCode [211] Add and Search Word - Data structure design

211. Design Add and Search Words Data Structure

Medium

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Constraints:

1 <= word.length <= 500
word in addWord consists lower-case English letters.
word in search consist of '.' or lower-case English letters.
At most 50000 calls will be made to addWord and search.

//C++: 46ms
class TrieNode {
public:
    bool isTail;
    char key;
    unordered_map<char, TrieNode*> children;

    // Initialize your data structure here.
    TrieNode():isTail(false){}
    TrieNode(char k):isTail(false),key(k){}
    
    bool findChild(char ch){
        return children.find(ch)!=children.end();
    }
    TrieNode * insertChildrend(char ch){
        TrieNode *newNode = new TrieNode(ch);
        children.insert(pair<char, TrieNode*>(ch, newNode));
        return newNode;
    }
    TrieNode * getChild(char ch){
        return children[ch];
    }
};


class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string s) {
        TrieNode *p = root;
        for(auto ch:s){
            if(!p->findChild(ch)){
                TrieNode *newNode = p->insertChildrend(ch);
                p = newNode;
            }else{
                p = p->getChild(ch);
            }
        }
        if(p!=NULL){
            p->isTail = true;
        }
    }

    // Returns if the word is in the trie.
    bool search(string key, TrieNode *p, int index) {
        if(index>key.size()) return false;
        if(index==key.size()){
            if(p!=NULL && p->isTail) return true;
            else return false;
        }
        char ch = key[index];
        if(ch!='.'){
            if(p==NULL || !p->findChild(ch)){
                return false;
            }
            TrieNode *q = p->getChild(ch);
            return search(key, q, index+1);
        }else{
            for(auto it=p->children.begin(); it!=p->children.end(); ++it){
                TrieNode *q = it->second;
                if(search(key, q, index+1)) return true;
            }
            return false;
        }
    }    

    TrieNode* root;
};


class WordDictionary {
    Trie trie;
public:
    WordDictionary(){
        Trie trie=Trie();
    }

    // Adds a word into the data structure.
    void addWord(string word) {
       trie.insert(word);
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return  trie.search(word, trie.root, 0);
    }
};

class TrieNode{
public:
    char key;
    bool isLeaf = false;
    TrieNode* children[26] = {NULL};
    TrieNode(){}
    TrieNode(char k):key(k){}
};

class Trie{
public:
    TrieNode *root = new TrieNode();
    Trie(){}
    void insert(string s){
        TrieNode *p = root;
        for(int i=0; i<(int)s.size(); ++i){
            char c = s[i];
            if(p->children[c-'a']==NULL){
                p->children[c-'a'] = new TrieNode(c);
            }
            p = p->children[c-'a'];
        }
        p->isLeaf = true;
    }

    bool search(string s){
        return search(s, s.size(), 0, root);
    }
    bool search(string s, int n, int i, TrieNode* p){
        if(i==n){
            return p->isLeaf;
        }else{
            char c = s[i];
            if(c!='.'){
                return p->children[c-'a']&&search(s, n, i+1, p->children[c-'a']);
            }else{
                for(char cc='a'; cc<='z'; ++cc){
                    if(p->children[cc-'a']&&search(s, n, i+1, p->children[cc-'a'])) return true;
                }
            }
            return false;
        }
    }
};

class WordDictionary {
    Trie trie;
public:

    // Adds a word into the data structure.
    void addWord(string word) {
        trie.insert(word);
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return trie.search(word);
    }
};