隐式图DFS(加复习)

Lintcode

680. Split String（）

strVariable.substring(start, end)
stringvar.substr(start , [length ])

class Solution {
public:
    /*
     * @param : a string to be split
     * @return: all possible split string array
     */
    vector<vector<string>> splitString(string& s) {
        // write your code here
        vector<vector<string>> results;
        vector<string> subsets;
        DFS(s, 0, subsets, results);
        return results;
    }
    void DFS(string& s, int index, vector <string>& subsets, vector<vector<string>>& results) {
        if (index == s.length()) {
            results.push_back(subsets);
            return;
        }
        string temp = s.substr(index, 1);
        subsets.push_back(temp);
        DFS(s, index + 1, subsets, results);
        subsets.pop_back();
        if (index + 1 == s.length()) {
            return;
        }
        temp = s.substr(index, 2);
        subsets.push_back(temp);
        DFS(s, index + 2, subsets, results);
        subsets.pop_back();
    }
};

Leetcode 17 Letter Combinations of a Phone Number
用ascll码计算， 还原int型,，记得char -》 int需要-‘0’

class Solution {
private:
    vector<vector<char>> table {{}, {}, {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'}, {'j', 'k', 'l'},
            {'m', 'n', 'o'}, {'p', 'q', 'r', 's'}, {'t', 'u', 'v'},{'w', 'x', 'y', 'z'} };
public:
    /**
     * @param digits: A digital string
     * @return: all posible letter combinations
     */
    vector<string> letterCombinations(string &digits) {
        // write your code here
        vector<string> result;
        if (digits == ""){
            return result;
        }
        string subset;
        DFS(digits, 0, result, subset);
        return result;

    }
    void DFS(string &digits, int index, vector<string> &result, string &subset){
        if (index == digits.size()){
            result.push_back(subset);
            return;
        }
        for (int i = 0; i < table[digits[index] - '0'].size(); i ++){
            subset.push_back(table[digits[index] - '0'][i]);
            DFS(digits, index + 1, result, subset);
            subset.pop_back();
        }
    }
};

class Solution {
private:
    vector<vector<char>> phone = { {}, {}, {'a','b','c'}, {'d','e','f'}, {'g','h','i'},{'j', 'k', 'l'}, {'m', 'n', 'o'},
                                  {'p', 'q', 'r', 's'}, {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'} };
public:
    vector<string> letterCombinations(string digits) {
        vector<string> results;
        if (digits == ""){
            return results;
        }
        vector<string> subsets;
        string temp;
        //cout<< "hello"<< endl<<temp;
        DFS(digits, 0, results, temp);
        return results;
    }
    void DFS(string digits, int index, vector<string>& results, string temp) {
        if (index == digits.length()) {
            results.push_back(temp);
            return;
        }
        char tempNumber = digits[index];
        for (char i : phone[tempNumber - '0']) {
           // temp = temp + i;
            DFS(digits, index + 1, results, temp+i);
           //// temp.pop_back();
        }
    }
};

153. Combination Sum II

每次要用一个数的时候一定要用第一个，所以中间有一个判断

class Solution {
public:
    /**
     * @param num: Given the candidate numbers
     * @param target: Given the target number
     * @return: All the combinations that sum to target
     */
    vector<vector<int>> combinationSum2(vector<int> &num, int target) {
        // write your code here
        vector<int> subset;
        vector<vector<int>> results;
        sort(num.begin(), num.end());
        DFS(num, target, 0, 0, subset, results);
        return results;
    }
    void DFS(vector<int> & num, int target, int tempSum, int index, vector<int> & subset, vector<vector<int>> & results){
        if (tempSum == target){
            results.push_back(subset);
            return;
        }
        if (index == num.size() || tempSum > target){
            return;
        }

        for (int i = index ; i < num.size(); i ++){
            if(i>index&&num[i]==num[i-1])continue;
            subset.push_back(num[i]);

            DFS(num, target, tempSum + num[i], i + 1, subset, results);
            subset.pop_back();
        }
    }
};

135. Combination Sum（数组去重）

class Solution {
public:
    /**
     * @param candidates: A list of integers
     * @param target: An integer
     * @return: A list of lists of integers
     */
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        // write your code here
        sort(candidates.begin(), candidates.end());
        candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());
        vector<int> subsets;
        vector<vector<int>> results;
        DFS(candidates, target, subsets, results, 0);
        return results;
    }
    void DFS(vector<int> & candidates, int target, vector<int> &subsets, vector<vector<int>> &results, int index){
        if(target == 0){
            results.push_back(subsets);
            return;
        }
        // if (index >= candidates.size()){
        //     return;
        // }
        if (target < 0){
            return;
        }
        for (int i = index; i < candidates.size(); i ++){
            subsets.push_back(candidates[i]);
            DFS(candidates, target - candidates[i], subsets, results, i);
            subsets.pop_back();
        }

    }
};

33. N-Queens

class Solution {
public:
    /*
    * @param n: The number of queens
    * @return: All distinct solutions
    */
    vector<vector<string>> solveNQueens(int n) {
        // write your code here
        unordered_map <string, unordered_set<int>> visited;
        vector<vector<int>> results;
        vector<int> subsets;
        DFS(n, visited, results, subsets, 0);
        //cout << results[0][0]<< endl;
        //cout << results.size() << results[0].size();
        vector<vector<string>> res = draw(results);
        return res;
    }
    void DFS(int n, unordered_map<string, unordered_set<int>> & visited, vector<vector<int>> & results, vector<int> &subsets, int row) {
        if (row == n) {
            results.push_back(subsets);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, visited)) {
                subsets.push_back(col);
                visited["col"].insert(col);
                visited["sum"].insert(col + row);
                visited["diff"].insert(row - col);
                DFS(n, visited, results, subsets, row + 1);
                visited["col"].erase(col);
                visited["sum"].erase(col + row);
                visited["diff"].erase(row - col);
                subsets.pop_back();
            }
        }
    }
    bool isValid(int row, int col, unordered_map<string, unordered_set<int>> & visited) {
        if (visited["col"].count(col) > 0) {
            return false;
        }
        if (visited["sum"].count(row + col) > 0) {
            return false;
        }
        if (visited["diff"].count(row - col) > 0) {
            return false;
        }
        return true;
    }
    vector<vector<string>> draw(vector<vector<int>> results) {
        vector<vector<string>> res;

        for (int j = 0; j < results.size(); j++) {
            vector<string> perRes;
            string temp;
            for (int i = 0; i < results[0].size(); i++) {
                temp.push_back('.');
            }
            for (int i = 0; i < results[0].size(); i++) {
                temp[results[j][i]] = 'Q';
                perRes.push_back(temp);
                temp[results[j][i]] = '.';
            }
            res.push_back(perRes);
        }


        return res;
    }
};

17. Subsets

class Solution {
public:
    /**
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    vector<vector<int>> subsets(vector<int> &nums) {
        // write your code here
        sort(nums.begin(), nums.end());
        vector<vector<int>> results;
        vector<int> subsets;
        DFS(nums, 0, results, subsets);
        return results;
    }
    void DFS(vector<int> &nums, int index, vector<vector<int>> &results, vector<int> &subsets){
        if (index == nums.size()){
            results.push_back(subsets);
            return;
        }
        DFS(nums, index + 1, results, subsets);
        subsets.push_back(nums[index]);
        DFS(nums, index + 1, results, subsets);
        subsets.pop_back();
    }
};

18. Subsets II(带重复)

class Solution {
public:
    /**
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        // write your code here
        sort(nums.begin(), nums.end());
        vector<vector<int>> results;
        vector<int> subsets;
        DFS(nums, 0, subsets, results, -1);
        return results;
    }
    void DFS(vector<int>& nums, int index, vector<int> &subsets, vector<vector<int>> & results, int old_index){
        if (index == nums.size()){
            results.push_back(subsets);
            return;
        }
        DFS(nums, index + 1, subsets, results, old_index);
        if (index > 0 && old_index != index - 1 && nums[index - 1] == nums[index]){
            return;
        }
        //DFS(nums, index + 1, subsets, results, old_index);
        subsets.push_back(nums[index]);
        DFS(nums, index + 1, subsets, results, index);
        subsets.pop_back();
    }
};

15. Permutations

class Solution {
public:
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int>> permute(vector<int> &nums) {
        // write your code here
        unordered_set<int> remain;
        vector<int> subsets;
        vector<vector<int>> results;
        for (int i = 0; i < nums.size(); i ++){
            remain.insert(nums[i]);
        }
        DFS(nums, remain, subsets, results);
        return results;
    }
    void DFS(vector<int> & nums, unordered_set<int> & remain, vector<int> & subsets, vector<vector<int>> & results){
        if (subsets.size() == nums.size()){
            results.push_back(subsets);
            return;
        }
        for (unordered_set<int>::iterator it = remain.begin(); it != remain.end(); it ++){
            int temp = *it;
            unordered_set<int> newSet = remain;
            subsets.push_back(*it);
            newSet.erase(*it);
            DFS(nums, newSet, subsets, results);
            subsets.pop_back();
            //remain.insert(temp);
        }
    }
};

829. Word Pattern II（hard）找对应字符串

class Solution {
public:
    /**
     * @param pattern: a string,denote pattern string
     * @param str: a string, denote matching string
     * @return: a boolean
     */
    bool wordPatternMatch(string &pattern, string &str) {
        // write your code here
        unordered_map <char, string> dict;
        unordered_set<string> used;

        return DFS(pattern, str, 0, 0, dict, used);
    }
    bool DFS(string & pattern, string & str, int strIndex, int patternIndex, unordered_map <char, string> & dict, unordered_set<string> &used){
        if (strIndex == str.size() && patternIndex == pattern.size()){
            // for(unordered_map <char, string> :: iterator it = dict.begin(); it != dict.end(); it++){
            //     cout << (*it).first << ' ' << (*it).second << endl;
            // }
            return true;
        }
        if (strIndex >= str.size() || patternIndex >= pattern.size()){
            return false;
        }
        char c = pattern[patternIndex];
        int remain_len = str.size() - strIndex;
        if (dict.count(c) > 0){
            if (remain_len < dict[c].size() || str.compare(strIndex, dict[c].size(), dict[c])){
                return false;
            }else{
                return DFS(pattern, str, strIndex + dict[c].size(), patternIndex + 1, dict, used);
            }
        }
        for (int i = 1; i <= remain_len; i ++){
            string temp = str.substr(strIndex, i);
            if (used.count(temp)){
                continue;
            }
            dict[c] = temp;
            used.insert(temp);
            if (DFS(pattern, str, strIndex + dict[c].size(), patternIndex + 1, dict, used)){
                return true;
            }
            dict.erase(c);
            used.erase(temp);
        }
        return false;
    }
};