Word Break II

Given a non-empty string s and a dictionary wordDictcontaining a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

============ Recursive (Time limit exceed) ==========

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        vector<string> sol;
        string ans;
        set<string> st(wordDict.begin(), wordDict.end());
        //helper(s, 0, ans, st, sol);
        sol = helperDynamic(s, st);
        return sol;
    }

    void helper(string s, int idx, string ans, set<string>& st,
                vector<string>& sol) {
        if (idx == s.size()) {
            sol.push_back(ans);
            return;
        }
        
        for (int i = idx; i < s.size(); i++) {
            string subStr = s.substr(idx, i - idx + 1);
            string strAns = ans;
            if (st.count(subStr)) {
                if (ans.empty()) {
                    ans = subStr;
                } else {
                    ans += " ";
                    ans += subStr;
                }

                helper(s, i + 1, ans, st, sol);
                ans = strAns;
            }
        }
        return;
    }
};

============= Dynamic  (Time limit exceed too) ============

    vector<string> append(vector<string> input, string s) {
        vector<string> ans;
        if (s.size() == 0) {
            return input;
        }
        for (auto str : input) {
            string newStr = str + " " + s;
            ans.push_back(newStr);
        }
        
        if (ans.size() == 0) {
            ans.push_back(s);
        }
        return ans;
    }
    
    vector<string> helperDynamic(string s, set<string>& st) {
        vector<string> ans;
        map<string, vector<string>> mp;
        
        for (int i = 0; i < s.size(); i++) {
            for (int j = i; j >= 0; j--) {
                string rightStr = s.substr(j, i - j + 1);
                if (!st.count(rightStr)) {
                    continue;
                }
                if (j == 0) {
                    mp[rightStr].push_back(rightStr);
                    continue;
                }
                string leftStr = s.substr(0, j);
                if (!mp.count(leftStr)) {
                    continue;
                }

                // Append new answer to the earlier computed one.
                vector<string> newAns = append(mp[leftStr], rightStr);

                 // Insert newAns into the existing solution.
                mp[leftStr + rightStr].insert(mp[leftStr + rightStr].end(),
                                             newAns.begin(), newAns.end());
            }
        }
        return (mp.count(s) != 0 ? mp[s] : ans);
    }


============== Dynamic (Memory limit exceed) ========
class Solution {
private:
    unordered_map<string, vector<string>> mp;
    
    vector<string> append(const vector<string>& input, const string& s) {
        vector<string> ans;
        if (s.size() == 0) {
            return ans;
        }
        for (const auto& str : input) {
            ans.push_back(str + " " + s);
        }
        return ans;
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st(wordDict.begin(), wordDict.end());
        return helperDynamic(s, st);
    }
    
    const vector<string>& helperDynamic(string s, unordered_set<string>& st) {
        for (int i = 0; i < s.size(); i++) {
            const string& partialStr = s.substr(0, i + 1);
            if (mp.count(partialStr)) {
                continue;
            }
            vector<string> ans;
            if (st.count(partialStr)) {
                ans.push_back(partialStr);
            }
            for (int j = i; j >= 0; j--) {
                const string& rightStr = s.substr(j, i - j + 1);
                if (!st.count(rightStr)) {
                    continue;
                }
                const string& leftStr = s.substr(0, j);

                // Append new answer to the earlier computed one.
                const vector<string>& newAns = append(mp[leftStr], rightStr);
                // Insert newAns into the existing solution.
                ans.insert(ans.end(), newAns.begin(), newAns.end());
            }
            mp[partialStr].swap(ans);
        }
        return mp[s];
    }

};

============== Recursive with memorization working solution =====
https://zxi.mytechroad.com/blog/leetcode/leetcode-140-word-break-ii/

=============== Beautiful recursion with memorization ==========
https://www.cnblogs.com/grandyang/p/4576240.html

================= Again ===========

class Solution {

public:

    vector<string> wordBreak(string s, vector<string>& wordDict) {

        vector<string> sol;

        string ans;

        unordered_set st(wordDict.begin(), wordDict.end());

        // recursive

        //helper(s, 0, st, ans, sol);

        //return sol;

        // Memoization..

        unordered_map<int, vector<string>> mp;

        return dp_helper(s, 0, st, mp);

    }

    

    vector<string> dp_helper(string s, int idx,

                             unordered_set<string>& st,

                             unordered_map<int, vector<string>> mp) {

        if (mp.count(idx) != 0) {

            return mp[idx];

        }

        vector<string> ans;

        for (int i = idx; i < s.size(); i++) {

            string str = s.substr(idx, i - idx + 1);

            if (st.count(str) != 0) {

                vector<string> remaining = dp_helper(s, i + 1, st, mp);

                if (remaining.size() == 0 && i != s.size() - 1) {

                    continue;

                }

                remaining = append_str(remaining, str);

                ans.insert(ans.end(), remaining.begin(), remaining.end());

            }

        }

        mp[idx] = ans;

        return mp[idx];

    }

    

    vector<string> append_str(vector<string>& input, string str) {

        vector<string> results;

        if (input.size() == 0) {

            results.push_back(str);

            return results;

        }

        for (auto& inp_str : input) {

            results.push_back(str + " " + inp_str);

        }

        return results;

    }

    

    void helper(string s, int idx, unordered_set<string>& st, string ans,

               vector<string>& sol) {

        if (idx == s.size() && ans.size() != 0) {

            sol.push_back(ans);

            return;

        }

        

        for (int i = idx; i < s.size(); i++) {

            string str = s.substr(idx, i - idx + 1);

            if (st.count(str) != 0) {

                string tmp = ans;

                if (ans.size() != 0) {

                    ans += " " + str;

                } else {

                    ans = str;

                }

                helper(s, i + 1, st, ans, sol);

                ans = tmp;

            }

        }

    }

};

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

1. You must return the copy of the given head as a reference to the cloned list.

/*

// Definition for a Node.

class Node {

public:

    int val;

    Node* next;

    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {

        val = _val;

        next = _next;

        random = _random;

    }

};

*/

class Solution {

public:

    Node* copyRandomList(Node* head) {

        map<Node*, Node *> mp;

        

        Node *new_node = NULL;

        new_node = copy(head, mp);

        

        process(new_node, head, mp);

        return new_node;

    }

    

    Node* copy(Node* head,map<Node*, Node*>& mp) {

        if (head == NULL) {

            return NULL;

        }

        Node *new_node = new Node(head -> val, NULL, head);

        mp[head] = new_node;

        new_node -> next = copy(head -> next, mp);

        return new_node;

    }

    

    void process(Node *new_node, Node *head, map<Node *, Node *>& mp) {

        Node *trav = new_node;

        while (trav != NULL) {

            trav -> random = (trav -> random -> random == NULL ? NULL : mp[trav -> random -> random]);

            trav = trav -> next;

        }

    }

};

================== Alternative one (without using map) ==========

1 -> 1' -> 2 -> 2' -> 3 -> 3'

node -> next -> random = (node -> random != NULL ? node -> random -> next : NULL);
node = node -> next -> next


===============

/*

// Definition for a Node.

class Node {

public:

    int val;

    Node* next;

    Node* random;

    

    Node(int _val) {

        val = _val;

        next = NULL;

        random = NULL;

    }

};

*/

class Solution {

public:

    Node* copyRandomList(Node* head) {

        if (head == NULL) {

            return NULL;

        }

        

        // Create a clone of every node

        Node *new_head = NULL;

        Node *temp = head;

        while (temp != NULL) {

            Node *temp_next = temp -> next;

            Node *new_node = new Node(temp -> val);

            new_node -> next = temp_next;

            temp -> next = new_node;

            temp = temp_next;

        }

        

        // Handle random assignment

        temp = head;

        while (temp != NULL && temp -> next != NULL) {

            temp -> next -> random =

                (temp -> random != NULL ? temp -> random -> next : NULL);

            temp = temp -> next -> next;

        }

        

        // Handle next assignment.

        temp = head;

        new_head = head -> next;

        while (temp != NULL && temp -> next != NULL) {

            Node *new_head_next = temp -> next;

            temp -> next = temp -> next -> next;

            new_head_next -> next =

                (temp -> next != NULL ? temp -> next -> next : NULL);

            temp = temp -> next;

        }

        return new_head;

    }

};

Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

================ Recursive ================

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        set<vector<int>> sol;
        vector<int> ans;
        int sum = 0;
        helper(candidates, target, sum, ans, sol);
        vector<vector<int>> sol_return(sol.begin(), sol.end());
        return sol_return;
    }
 
    void helper(vector<int>& candidates, int target, int sum, vector<int> ans,
               set<vector<int>>& sol) {
        if (sum > target) {
            return;
        }
     
        if (sum == target) {
            sort(ans.begin(), ans.end());
            sol.insert(ans);
            return;
        }
     
        for (int num : candidates) {
            if (sum + num <= target) {
                ans.push_back(num);
                sum += num;
                helper(candidates, target, sum, ans, sol);
                sum -= num;
                ans.pop_back();
            }
        }
        return;
    }
};


=========== efficient one ========
class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> ans; vector<int> vec; sort(candidates.begin(), candidates.end()); heleper(candidates, ans, vec, 0, target); return ans; } void heleper(vector<int> candidates, vector<vector<int>> &ans, vector<int> &vec, int start, int target) { if (target == 0) { ans.push_back(vec); return; } for (int i = start; i < candidates.size() && target - candidates[i] >= 0; i++) { vec.push_back(candidates[i]); heleper(candidates, ans, vec, i, target - candidates[i]); vec.pop_back(); } } };

Vertical Order Traversal of a Binary Tree

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate.  Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

Note:

1. The tree will have between 1 and 1000 nodes.
2. Each node's value will be between 0 and 1000.

 ===================== Pre order traversal is not the right approach here =======

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if (root == NULL) {
            return vector<vector<int>>();
        }
        vector<vector<int>> ans;
        map<int, vector<int>> mp;
        helper(root, 0, mp);
        generate(mp, ans);
        return ans;
    }
 
    void helper(TreeNode* root, int location, map<int, vector<int>>& mp) {
        if (root == NULL) {
            return;
        }
        mp[location].push_back(root -> val);
        helper(root -> left, location - 1, mp);
        helper(root -> right, location + 1, mp);
        return;
    }
 
    void generate(map<int, vector<int>>& mp, vector<vector<int>>& ans) {
        map<int, vector<int>>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++) {
            ans.push_back(it -> second);
        }
        return;
    }
};


========== . Queue is not working as well =====

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if (root == NULL) {
            return vector<vector<int>>();
        }
        vector<vector<int>> ans;
        map<int, vector<int>> mp;
        helper(root, 0, mp);
        generate(mp, ans);
        return ans;
    }
 
    void helper(TreeNode* root, int location, map<int, vector<int>>& mp) {
        if (root == NULL) {
            return;
        }
        queue<pair<int, TreeNode*>> q;
        q.push(make_pair(0, root));
     
        while (!q.empty()) {
            pair<int, TreeNode*> node = q.front(); q.pop();
            mp[node.first].push_back(node.second -> val);
            if (node.second -> left) {
                q.push(make_pair(node.first - 1, node.second -> left));
            }
            if (node.second -> right) {
                q.push(make_pair(node.first + 1, node.second -> right));
            }
        }
    }
 
    void generate(map<int, vector<int>>& mp, vector<vector<int>>& ans) {
        map<int, vector<int>>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++) {
            ans.push_back(it -> second);
        }
        return;
    }
};

================== Right one ============
class Solution
{
    public:
    vector<vector<int>> verticalTraversal(TreeNode* root)
    {
        vector<vector<int>> result;
        map<int,map<int,vector<int>>> total;
        deque<TreeNode*> q;
        deque<int> p;
        deque<int> h;
        q.push_back(root);
        p.push_back(0);
        h.push_back(0);
        while(q.size()>0)
        {
            TreeNode* c=q.front();
            int x=p.front();
            int y=h.front();
            q.pop_front();
            p.pop_front();
            h.pop_front();
            total[x][y].push_back(c->val);
            if(c->left!=NULL)
            {
                q.push_back(c->left);
                p.push_back(x-1);
                h.push_back(y+1);
            }
            if(c->right!=NULL)
            {
                q.push_back(c->right);
                p.push_back(x+1);
                h.push_back(y+1);
            }
        }
        for(map<int,map<int,vector<int>>>::iterator it1=total.begin();it1!=total.end();it1++)
        {
            vector<int> temp;
            for(map<int,vector<int>>::iterator it2=it1->second.begin();it2!=it1->second.end();it2++)
            {
                sort(it2->second.begin(),it2->second.end());
                for(int i=0;i<it2->second.size();i++)
                {
                    temp.push_back(it2->second[i]);
                }
            }
            result.push_back(temp);
        }
        return result;
    }
};

Random Pick with Weight

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

Note:

1. 1 <= w.length <= 10000
2. 1 <= w[i] <= 10^5
3. pickIndex will be called at most 10000 times.

Example 1:

Input: 
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]

Example 2:

Input: 
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]

// Prefix Sum + Binary search

class Solution {
    private:
        vector<int> data;
public:
    Solution(vector<int>& w) {
        data = w;
        for (int i = 1; i < w.size(); i++) {
            data[i] = data[i -1] + w[i];
        }
    }
   
    int pickIndex() {
        int size = data.size();
        int random = rand() % data.back() + 1;
        int st = 0, end = size - 1;
        while (st < end) {
            int mid = st + (end - st) / 2;
            if (data[mid] == random) {
                return mid;
            } else if (data[mid] < random) {
                st = mid + 1;
            } else {
                end = mid;
            }
        }
        return st;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

class Solution {
public:
    int binary_helper(int dividend, int divisor) {
        long divd = abs((long)dividend);
        long div = abs((long)divisor);
        int ans = 0;
        while (true) {
            int partial_ans = 0;
            long new_div = div;
            if (divd == div) {
                return ans + 1;
            } else if (divd < div) {
                return ans;
            }
            while(true) {
                if ((new_div << 1) > divd) {
                    break;
                }
                new_div <<= 1;
                partial_ans++;
            }
            if (partial_ans == 0) {
                ans += 1;
                break;
            }
            divd -= new_div;
            ans += (1 << partial_ans);
        }
        return ans;
    }
 
    int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return INT_MAX;
        }
             
        if (dividend == INT_MIN) {
            if (divisor == 1) {
                return INT_MIN;
            } else if (divisor == -1) {
                return INT_MAX;
            }
        }

        int sign_a = (dividend < 0 ? -1 : 1);
        int sign_b = (divisor < 0 ? -1 : 1);

        //int ans = linear_helper(dividend, divisor);
        int ans = binary_helper(dividend, divisor);
        return ans * sign_a * sign_b;
    }
 
    long linear_helper(int dividend, int divisor) {
        long divd = abs((long)dividend);
        long div = abs((long)divisor);
        long count = 0;
        while (divd >= div) {
            count++;
            divd -= div;
        }
        return count;
    }
};




============== Cleaner one ===========

public int divide(int dividend, int divisor) {
    //handle special cases
    if(divisor==0) return Integer.MAX_VALUE;
    if(divisor==-1 && dividend == Integer.MIN_VALUE)
        return Integer.MAX_VALUE;
 
    //get positive values
    long pDividend = Math.abs((long)dividend);
    long pDivisor = Math.abs((long)divisor);
 
    int result = 0;
    while(pDividend>=pDivisor){
        //calculate number of left shifts
        int numShift = 0;    
        while(pDividend>=(pDivisor<<numShift)){
            numShift++;
        }
 
        //dividend minus the largest shifted divisor
        result += 1<<(numShift-1);
        pDividend -= (pDivisor<<(numShift-1));
    }
 
    if((dividend>0 && divisor>0) || (dividend<0 && divisor<0)){
        return result;
    }else{
        return -result;
    }
}

============= Another ======

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        int sign = 1;
        if (dividend < 0) {
            sign *= -1;
        }
        if (divisor < 0) {
            sign *= -1;
        }
        // return sign;
        if (dividend == 0 || divisor == 0) {
            return 0;
        }
        
        long temp = labs(dividend);
        long tempDiv = labs(divisor);
        if (temp == tempDiv) {
            return sign;
        }
        
        long ans = 0;
        while (temp != 0) {
            int k = 0;
            while ((tempDiv << k) <= temp) {
                k++;
            }
            if (k == 0) {
                return sign * ans;
            }
            ans += (1 << (k - 1));
            temp -= (tempDiv << (k - 1));
        }
        return  sign == 1 ? ans : -ans;
    }
};