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(); } } };