047. Permutations II

Difficulty: Medium

Frequency: N/A

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> results;
        vector<int> tmp;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        permuteHelper(nums, used, tmp, results);
        return results;
    }
    void permuteHelper(vector<int> nums, vector<bool> used, vector<int> tmp, vector<vector<int>> &results) {
        if(tmp.size() == nums.size()) {
            results.push_back(tmp);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if(used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            tmp.push_back(nums[i]);
            permuteHelper(nums, used, tmp, results);
            tmp.pop_back();
            used[i] = false;
        }
    }
};

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

Things to learn:
1. How to skip duplicate element
2. Avoid using lookup from previous result set.

089. Gray Code

Difficulty: Medium

Frequency: N/A

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.


My solution:
Data structure:
vector
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        result.push_back(0);
        for (int i = 0; i < n; i++) {
            int highBit = 1 << i;
            for (int j = result.size() - 1; j >= 0; j--) {
                result.push_back(highBit + result[j]);
            }
        }
        return result;
    }
};

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

Things to learn:
1. How to do it in backtracking way?

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:

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:

227. Basic Calculator II

Difficulty:  Medium

Frequency:  N/A

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.


My solution:
Data structure:
string
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:
class Solution {
public:
    int calculate(string s) {
        istringstream input('+' + s + '+');
        int result = 0, curr = 0, next;
        char op;
        while (input >> op) {
            if (op == '+' || op == '-') {
                result += curr;
                input >> curr;
                curr = op == '+' ? curr : -curr;
            } else {
                input >> next;
                if (op == '*') curr *= next;
                else curr /=next;
            }
        }
        return result;
    }
};

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

Things to learn:

273. Integer to English Words

Difficulty: Medium

Frequency: 

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 – 1.

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Hint:

  1. Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.
  2. Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.
  3. There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

My solution:
Data structure:
string, unordered_map
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
1. 0
2. 1000010
3. 10
4. 30
5. 100
6. 1000
Code:
class Solution {
public:
    string digits[20] = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    string tens[10] = {"Zero", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

    string int2string(int n) {
        if (n >= 1000000000) {
            return int2string(n / 1000000000) + " Billion" + int2string(n % 1000000000);
        } else if (n >= 1000000) {
            return int2string(n / 1000000) + " Million" + int2string(n % 1000000);
        } else if (n >= 1000) {
            return int2string(n / 1000) + " Thousand" + int2string(n % 1000);
        } else if (n >= 100) {
            return int2string(n / 100) + " Hundred" + int2string(n % 100);
        } else if (n >= 20) {
            return  " " + tens[n / 10] + int2string(n % 10);
        } else if (n >= 1) {
            return " " + digits[n];
        } else {
            return "";
        }
    }

    string numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        } else {
            string ret = int2string(num);
            return ret.substr(1, ret.length() - 1);
        }
    }
};

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

Things to learn:

271. Encode and Decode Strings

Difficulty: Medium

Frequency: 

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Note:

  • The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
  • Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
  • Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

My solution:
Data structure:
string, vector
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Codec {  
public:  
  
    // Encodes a list of strings to a single string.  
    string encode(vector<string>& strs) {  
        string s = "";  
        for(auto i : strs) {  
            s += to_string(i.length()) + "#" + i;  
        }  
        return s;  
    }  
  
    // Decodes a single string to a list of strings.  
    vector<string> decode(string s) {  
        vector<string> str;  
        int i = 0;  
        while(i < s.length()) {  
            int sharp = s.find("#", i);  
            int l = stoi(s.substr(i, sharp - i));  
            str.push_back(s.substr(sharp + 1, l));  
            i = sharp + l + 1;  
        }  
        return str;  
    }  
};  

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

Things to learn:

049. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.


Questions:

1. results need to be sorted or not.
2. upper case and lower case consideration.

Test cases:

1. empty input

2. single input

3. all different anagrams

4. all same anagram

5. normal case


 Solution 1:

Data structure:
string, vector, unordered_map
Method:
hash table
Steps:
1. for each string, sort it.
2. add the original string to the hash table with sorted string as key.
Complexity:
runtime: O(NlogN)
space:O(N)
Code:
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> myMap;
        //loop through the input
        for (auto str : strs) {
            string s = str;
            sort(s.begin(), s.end());
            myMap[s].push_back(str);
        }

        //construct the results
        vector<vector<string>> results;
        for (auto iter : myMap) {
            results.push_back(iter.second);
        }
        return results;
    }
};

Solution 2:
Data structure:
array, string, unordered_map
Method:
hash table
steps:
1. generate a unique string from the input string as a key
2. insert into the hash table
Complexity:
runtime: O(N)
space: O(N)
Code:
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> myMap;
        //loop through the input strings
        for (string str : strs) {
            //construct the key based on the number of characters in the string
            vector<int> cnt(26, 0);
            string key = "";
            for (char c : str) {
                ++cnt[c - 'a'];
            }
            for (int i : cnt) {
                key += to_string(i) + "#";
            }
            myMap[key].push_back(str);
        }

        //construct the results
        vector<vector<string>> results;
        for (auto iter : myMap) {
            results.push_back(iter.second);
        }

        return results;
    }
};

Things to learn:
1. the way to generate the key in solution 2 is interesting. For infinite input, there may be an easier solution.

249. (Locked)Group Shifted Strings

Difficulty:  Easy

Frequency: N/A

Given a string, we can “shift” each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep “shifting” which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

Note: For the return value, each inner list’s elements must follow the lexicographic order.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {  
public:  
    vector<vector<string>> groupStrings(vector<string>& strings) {  
        unordered_map<string, vector<string>> d;  
        for(int i = 0; i < strings.size(); i++) {  
            string s = "";  
            for(int j = 0; j < strings[i].size(); j++) {  
                s += to_string(((strings[i][j] - strings[i][0]) + 26) % 26) + " ";  
            }  
            if(d.find(s) != d.end()) {  
                d[s].push_back(strings[i]);  
            } else {  
                vector<string> v;  
                v.push_back(strings[i]);  
                d.insert(pair<string, vector<string>>(s, v));  
            }  
        }  
          
        vector<vector<string>> results;
        for(vector<vector<string>>::iterator i = d.begin(); i != d.end(); i++) {  
            sort(i->second.begin(), i->second.end());  
            results.push_back(i->second);  
        }  
        return results;  
    }  
};  

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

Things to learn: