046. Permutations

Difficulty: 

Frequency: 

Given a collection of distinct 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].


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> results;
        vector<int> tmp_vec;
        permute_helper(nums, results, tmp_vec);
        return results;
    }
    void permute_helper(vector<int> nums, vector<vector<int>> &results, vector<int> tmp_vec) {
        if (nums.empty()) {
            results.push_back(tmp_vec);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            tmp_vec.push_back(nums[i]);
            vector<int> new_nums = nums;
            new_nums.erase(new_nums.begin() + i);
            permute_helper(new_nums, results, tmp_vec);
            tmp_vec.pop_back();
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

320. (locked)Generalized Abbreviation

Difficulty: Medium

Frequency: N/A

Write a function to generate the generalized abbreviations of a word.
Example:
Given word = "word", return the following list (order does not matter):
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
        vector<string> generateAbbreviations(string word) {
                vector<string> results;
                string tmp;
                helper(word, 0, tmp, results);
                return results;
        }
        void helper(string word, int idx, string tmp, vector<string> &results) {
                if (idx == word.size()) {
                        results.push_back(tmp);
                        return;
                }
                helper(word, idx + 1, tmp + word[idx], results);
                for (int i = 1; i < word.size() - idx; i++)
                        helper(word, idx + 1 + i, tmp + to_string(i) + word[idx + 1], results);
                helper(word, word.size(), tmp + to_string(word.size() - idx), results);
        }
};


Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

294. (locked)Flip Game II

Difficulty: Medium

Frequency: N/A

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm’s runtime complexity.


My solution:
Data structure:
string, backtracking
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    bool canWin(string s) {
        for (int i = -1; i = s.find("++", i + 1) >= 0; ) {
            if(!canWin(s.substr(0, i) + "--" + s.substr(i + 2)))
                return true;
        } 
        return false;
    }
}

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: