LIKE CODING: Data structure

Vector2D iterator = new Vector2D([[1,2],[3],[4]]);

iterator.next(); // return 1
iterator.next(); // return 2
iterator.next(); // return 3
iterator.hasNext(); // return true
iterator.hasNext(); // return true
iterator.next(); // return 4
iterator.hasNext(); // return false

Notes:

Please remember to RESET your class variables declared in Vector2D, as static/class variables are persisted across multiple test cases. Please see herefor more details.
You may assume that next() call will always be valid, that is, there will be at least a next element in the 2d vector when next() is called.

Follow up:

As an added challenge, try to code it using only iterators in C++ or iterators in Java.

class Vector2D
{
    vector<vector<int>>::iterator row_it, row_end;
    vector<int>::iterator col_it;

  public:
    Vector2D(vector<vector<int>> &v)
    {
        row_it = v.begin(), row_end = v.end();
        while (row_it != row_end && row_it->empty())
            row_it++;
        if (row_it != row_end)
            col_it = row_it->begin();
    }

    int next()
    {
        int v = *col_it;
        col_it++;
        if (col_it == row_it->end())
        {
            row_it++;
            while (row_it != row_end && row_it->empty())
                row_it++;
            if (row_it != row_end)
                col_it = row_it->begin();
        }
        return v;
    }

    bool hasNext()
    {
        return row_it != row_end;
    }
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(v);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

Tuesday, August 4, 2015

LeetCode [244] Shortest Word Distance II

Ref
[1] https://leetcode.com/problems/shortest-word-distance-ii/
OJ

Wednesday, May 13, 2015

LeetCode [208] Implement Trie (Prefix Tree)

208. Implement Trie (Prefix Tree)

Medium

Trie (we pronounce "try") or prefix tree is a tree data structure used to retrieve a key in a strings dataset. There are various applications of this very efficient data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() initializes the trie object.
void insert(String word) inserts the string word to the trie.
boolean search(String word) returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

1 <= word.length, prefix.length <= 2000
word and prefix consist of lowercase English letters.
At most 3 * 104 calls will be made to insert, search, and startsWith.

class Trie {
    class TrieNode{
        boolean isEnd;
        TrieNode[] children;
        TrieNode(){
            isEnd = false;
            children = new TrieNode[26];
        }
    }
    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode p = root;
        for(char c : word.toCharArray()){
            if(p.children[c-'a']==null){
                p.children[c-'a'] = new TrieNode();
            }
            p = p.children[c-'a'] ;
        }
        p.isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode p = root;
        for(char c : word.toCharArray()){
            if(p.children[c-'a']==null){
                return false;
            }
            p = p.children[c-'a'] ;
        }
        return p.isEnd == true;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for(char c : prefix.toCharArray()){
            if(p.children[c-'a']==null){
                return false;
            }
            p = p.children[c-'a'] ;
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Tuesday, February 3, 2015

LeetCode [170] Two Sum III - Data structure design

Ref
[1] https://leetcode.com/problems/two-sum-iii-data-structure-design/
OJ