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?
Advertisements

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:

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:

017. Letter Combinations of a Phone Number

Difficulty: Medium

Frequency: N/A

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.


My solution:
Data structure:
vector, string
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return vector<string>();
        vector<string> results;
        results.push_back("");
        unordered_map<char, string> mapping = {{'0', ""},
                                              {'1', ""},
                                              {'2', "abc"},
                                              {'3', "def"},
                                              {'4', "ghi"},
                                              {'5', "jkl"},
                                              {'6', "mno"},
                                              {'7', "pqrs"},
                                              {'8', "tuv"},
                                              {'9', "wxyz"}};

        for (int i = 0; i < digits.size(); i++) {
            string curr = mapping[digits[i]];
            if(!curr.size()) continue;
            vector<string> tmp;
            for (int j = 0; j < results.size(); j++) {
                for (int k = 0; k < curr.size(); k++) {
                    tmp.push_back(results[j] + curr[k]);
                }
            }
            results.swap(tmp);
        }
        return results;
    }
};

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

Things to learn:
1. swap() is interesting.
2. Try backtracking.