[LintCode] Add and Search Word

Design a data structure that supports the following two operations:addWord(word) and 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.

Example

addWord("bad")
addWord("dad")
addWord("mad")
search("pad")  // return false
search("bad")  // return true
search(".ad")  // return true
search("b..")  // return true

Note

You may assume that all words are consist of lowercase letters a-z.

class Trie {
    unordered_map<char,Trie*> _map;
    bool _end;
public:
    Trie() {
        _end = false;
    }
    void add(string &s,int n) {
        if(!_map.count(s[n])) {
            _map[s[n]] = new Trie();
        }
        if(n == s.length() - 1) {
            _map[s[n]]->_end = true;
        } else {
            _map[s[n]]->add(s, n+1);
        }
    }
    
    bool search(string &s, int n){
        if(s.length() -1 == n) {
            if(s[n] == '.') {
                for(auto e : _map) {
                    if(e.second->_end) return true;
                }
                return false;
            }
            return _map.count(s[n]) ? _map[s[n]]->_end : false;
        }
        if(s[n] == '.') {
            for(auto e : _map) {
                if(e.second->search(s, n+1)) {
                    return true;
                }
            }
        } else {
            if(!_map.count(s[n])) return false;
            return _map[s[n]]->search(s, n+1);
        }
        return false;
    }
};

class WordDictionary {
    Trie _trie;
public:
    void addWord(string word) {
        _trie.add(word, 0);
    }
    bool search(string word) {
        return _trie.search(word, 0);
    }
};

[LintCode] Restore IP Addresses Show result

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example

Given "25525511135", return

[
  "255.255.11.135",
  "255.255.111.35"
]

Order does not matter.

class Solution {
public:
    vector<string> helper(string s, int n) {
        int l = s.length();
        vector<string> res;
        
        if(3*n < l || n>l) {
            return res;
        }
        
        if(n == 1){
            if(l>1 && s[0] == '0') return res;
            if(stoi(s)<=255) {
                res.push_back(s);
            }
            return res;
        }
        
        for(int i=1;i<=3 && i<l;i++){
            string t = s.substr(0,i);
            if((i>1 && s[0] == '0') || 
                (i == 3 && stoi(t)>255)) break;
            vector<string> pp = helper(s.substr(i), n-1);
            for(auto e:pp) {
                res.push_back(t+"."+e);
            }
        }
        return res;
    }
    
    vector<string> restoreIpAddresses(string& s) {
        // Write your code here
        return helper(s, 4);
    }
};

LFU Cache

Similar to LRU http://techinpad.blogspot.com/2015/06/leetcode-lru-cache.html, implement a LFU, which is the least frequently used cache.

Analysis: multimap should be the best data structure to use.

class LFUCache{
    unordered_map<int, multimap<int, pair<int,int>>::iterator> mMap;
    multimap<int, pair<int,int>> mList;
    int mCap;
public:
    LFUCache(int capacity) {
        mCap = capacity;
    }
    
    void moveToHead(int key) {
        multimap<int, pair<int,int>>::iterator it = mMap[key];
        pair<int, pair<int,int>> n(it->first+1, pair<int,int>(it->second.first, it->second.second));
        mList.erase(it);
        mMap[key] = mList.insert(n);
    }
    
    int get(int key) {
        if(!mMap.count(key)) return -1;
        moveToHead(key);
        return mMap[key]->second.second;
    }
    
    void set(int key, int value) {
        
        if(mMap.count(key)) {
            mMap[key]->second.second = value;
            moveToHead(key);
            return;
        } 
        
        if(mList.size() == mCap) {
            auto it = mList.begin();
            mMap.erase(it->second.first);
            mList.erase(it);
        }
        pair<int,pair<int,int>> n(1, pair<int,int>(key, value));
        mMap[key] = mList.insert(n);
        
    }
};

[LeetCode] Serialize and Deserialize Binary Tree

Question can be found
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == NULL) return "";
        vector<string> v;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode *t = q.front();
            q.pop();
            if(t == NULL) {
                v.push_back("null");
                continue;
            }
            
            v.push_back(to_string(t->val));
            
            q.push(t->left);
            q.push(t->right);
        }
        
        int l = v.size() - 1;
        while(v[l] == "null") l--;
        
        string res = v[0];
        for(int i=1;i<=l;i++){
            res += "," + v[i];
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(0 == data.length()) return NULL;
        vector<string> v;
        int start = 0;
        for(int i=1;i<data.length();i++) {
            if(data[i] != ',') continue;
            v.push_back(data.substr(start, i-start));
            start = i+1;
        }
        v.push_back(data.substr(start));
        int index = 0;
        
        TreeNode *node = new TreeNode(stoi(v[index]));
        
        queue<TreeNode*> nodesOnLevel;
        int count = v.size();
        nodesOnLevel.push(node);
        
        while(!nodesOnLevel.empty()) {
            int size = nodesOnLevel.size();
            for(int i=0;i<size;i++){
                
                int left = index + 1;
                if(left >= count) return node;
                if(v[left] != "null") {
                    TreeNode *cur = new TreeNode(stoi(v[left]));
                    nodesOnLevel.front()->left = cur;
                    nodesOnLevel.push(cur);
                }
                
                int right = index + 2;
                if(right >= count) return node;
                if(v[right] != "null") {
                    TreeNode *cur = new TreeNode(stoi(v[right]));
                    nodesOnLevel.front()->right = cur;
                    nodesOnLevel.push(cur);
                }
                nodesOnLevel.pop();
                index += 2;
            }
        }
        
        return node;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

[LeetCode] Find Median from Data Stream

Question can be found https://leetcode.com/problems/find-median-from-data-stream/

class MedianFinder {
    priority_queue<int> up;
    priority_queue<int, vector<int>, greater<int> > down;
public:
    // Adds a number into the data structure.
    void addNum(int num) {
        if(up.empty() || num <= up.top()) {
            up.push(num);
        }
        else if(down.empty() || num >= down.top()) {
            down.push(num);
        }
        else {
            up.push(num);
        }

        if(up.size() >= down.size() + 2) {
            int t = up.top();
            up.pop();
            down.push(t);
        }
        else if(down.size() >= up.size() + 2){
            int t = down.top();
            down.pop();
            up.push(t);
        }
    }
    // Returns the median of current data stream
    double findMedian() {
        if(up.size() > down.size()) return up.top();
        else if(down.size() > up.size()) return down.top();
        return (up.top() + down.top())/2.0;
    }
};