Day 32, 30,39,46, Substring with Concatenation of All Words, Combination Sum,Permutations

Substring with Concatenation of All Words
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
------------------------------------------------------------------------
use two maps to count occurrences of all patterns, iterate through S to check if each word in L exactly occurs once in current part of S
solution is from internet
this is a boring and tasteless question
time and space complexity?
notice the conversion (int)S.size() in for loop

class Solution {  
public:  
    vector<int> findSubstring(string S, vector<string> &L) {  
        map<string, int> words;  
        map<string, int> curStr;  
        for(int i = 0; i < L.size(); ++i)  
            ++words[L.at(i)];  
        int N = L.size();  
        vector<int> ret;  
        if(N <= 0)   return ret;  
        int M = L.at(0).size();  
        for(int i = 0; i <= (int)S.size()-N*M; ++i)  
        {  
            curStr.clear();  
            int j = 0;  
            for(j = 0; j < N; ++j)  
            {  
                string w = S.substr(i+j*M, M);  
                if(words.find(w) == words.end())  
                    break;  
                ++curStr[w];  
                if(curStr[w] > words[w])  
                    break;  
            }  
            if(j == N)  ret.push_back(i);  
        }  
        return ret;  
    }  
};

Update on Sep-11-2014
The idea is similar to Longest Substring Without Repeating Characters. Each word has the same length and can be seen as a unique(or not) character.
A slightly different implementation is it can re-assign a new map at the beginning of outer loop.
Update on Feb-17-2015
COME_BACK
inner loop里的算法
#1 如果找不到当前word，重新设置map和start，重新开始
#2 如果找到且数量 > 0
#3 如果找到且数量 == 0: 从start开始pop旧的word，直到找到当前的为止

因为所有词为无序，不用保证维护当前的数组， 如
1 - 2 -..........3 - 2 - 1, 假设扫到3时已经找到所有的词

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> dic;
        for (int i = 0; i < words.size(); i++) {
            if (dic.find(words[i]) == dic.end()) {
                dic[words[i]] = 1;
            }else {
                dic[words[i]]++;
            }
        }
        
        vector<int> rt;
        int wordLen = words[0].length();

        for (int i = 0; i < wordLen; i++) {
            int start = i,count = 0;
            unordered_map<string,int> temp = dic;
            for (int j = i; j < s.length(); j += wordLen) {
                string word = s.substr(j,wordLen);
                if (temp.find(word) == temp.end()) {
                    count = 0;
                    temp = dic;
                    start = j + wordLen;
                    continue;
                }else if (temp[word] > 0) {
                    temp[word]--;
                    count++;
                    if (count == words.size()) rt.push_back(start);
                }else if (temp[word] == 0) {
                    while (true) {
                        string begin = s.substr(start,wordLen);
                        if (begin == word) {
                            start += wordLen;
                            if (count == words.size()) rt.push_back(start);
                            break;
                        }
                        temp[begin]++;
                        count--;
                        start += wordLen;
                    }
                }
            }    
        }
        
        return rt;
    }
};

Java, updated on Sep-25th-2018
3种情况：
1. map有单词且次数大于0
2. map有单词但次数等于0
3. map不包含单词
2和3可以揉成一个branch

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        
        Map<String, Integer> map = getMap(words);
        List<Integer> rt = new ArrayList<>();
        if (s.length() == 0 || words.length == 0) return rt;
        
        for (int i = 0; i < words[0].length(); i++) {
            rt.addAll(findSub(s, i, map, words[0].length(), words.length));    
        }
        
        return rt;
    }
    
    private List<Integer> findSub(String s, int i, Map<String, Integer> map, int len, int count) {
        List<Integer> rt = new ArrayList<>();
        Map<String, Integer> local = new HashMap<>(map);
        int start = i;
        int tempCount = count;
        
        while (i < s.length() - len + 1) {
            String word = s.substring(i, i + len);
            if (local.containsKey(word) && local.get(word) > 0) {
                local.put(word, local.get(word) - 1);
                i += len;
                tempCount--;
                
                if (tempCount == 0) {
                    rt.add(start);
                    String old = s.substring(start, start + len);
                    local.put(old, local.get(old) + 1);
                    start += len;
                    tempCount++;
                }
            }else {
                while (true) {
                    String old = s.substring(start, start + len);
                    if (old.equals(word)) {
                        start += len;
                        break;
                    }
                    local.put(old, local.get(old) + 1);
                    start += len;
                    tempCount++;
                }   
                i += len;
            }
        }
        
        return rt;
    }
    
    private Map<String, Integer> getMap(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        
        return map;
    }
}
}

Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, � , a_k) must be in non-descending order. (ie, a₁ ? a₂ ? � ? a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
-------------------------------------------------------------
combination

class Solution {
public:
    void comb (vector<int> &candidates, int target,vector<vector<int> > &ret,vector<int> cur,int start) {
        if (target == 0) {
            ret.push_back(cur);
        }else {
            for (int i=start;i<candidates.size();i++) {
                if (target - candidates[i] >= 0) {
                    vector<int> v = cur;  // Attention here!!!
                    v.push_back(candidates[i]);
                    comb(candidates,target-candidates[i],ret,v,i);
                }
            }
        }
    }

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sort(candidates.begin(),candidates.end());
        vector<vector<int> > ret;
        vector<int> cur;
        comb(candidates,target,ret,cur,0);
        return ret;
    }
};

class Solution {
public:
    void comb(vector<vector<int> > &rt, vector<int> &candidates, vector<int> cur, int target, int index) {
        if (target == 0) {
            rt.push_back(cur);
            return;
        } 
        if (index >= candidates.size() || target < 0) return;
        
        comb(rt,candidates,cur,target,index + 1);
        cur.push_back(candidates[index]);
        comb(rt,candidates,cur,target - candidates[index],index);
    } 

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<vector<int> > rt;
        vector<int> cur;
        comb(rt,candidates,cur,target,0);
        
        return rt;
    }
};

Permutations
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
--------------------------------------------------------------------

class Solution {
public:
    void per (vector<int> num,vector<int> cur,vector<vector<int> > &ret) {
        if (num.size() == 0) {
            ret.push_back(cur);
        }
        for (int i=0;i<num.size();i++) {
            vector<int> v = cur;
            vector<int> w = num;
            v.push_back(w[i]);
            w.erase(w.begin()+i);
            per(w,v,ret);
        }
    }

    vector<vector<int> > permute(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > ret;
        vector<int> cur;
        per(num,cur,ret);
        return ret;
    }
};

#1 以index为分界线，来区分已经使用和未使用的集合（此条不一定为正确，需看代码）
#2 换句话说，每一个recursive call，都遍历所有未使用的数字确定在index（n次）
index = 0: 123, 213, 321
index = 1: 132, 231, 312
index = 2: 插入

class Solution {
public:
    void swap(vector<int> &nums,int i,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    void per(vector<vector<int> > &rt, vector<int> &nums, int index) {
        if (nums.size() == index) {
            rt.push_back(nums);
            return;
        }
        
        for (int i = index; i < nums.size(); i++) {
            swap(nums,i,index);
            per(rt,nums,index + 1);
            swap(nums,i,index); // 此行可以不加，结果同样正确，因为每一次都会确定一个数
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > rt;
        per(rt,nums,0);
        
        return rt;
    }
};