# 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:

# 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) {
return encoded_string;
}```

Machine 2 (receiver) has the function:

```vector<string> decode(string s) {
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]) + 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.