#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <unordered_map>
using std::unordered_map;
using std::vector;
using std::string;
using std::queue;
class Solution {
public:
void permutationHelper(unordered_map<char, int> & m, vector<string> & res, string & chosen, int len){
if (chosen.size() == len){
res.push_back(chosen);
return;
}
for (auto & it : m){
// choose
if (it.second == 0)
continue;
else {
// choose
chosen.push_back(it.first);
it.second--;
// explore
permutationHelper(m, res, chosen, len);
// unchoose
chosen.pop_back();
it.second++;
}
}
}
vector<string> permutations(string set) {
// write your solution here
unordered_map<char, int> m;
for (char c : set){
m[c]++;
}
vector<string> res;
int len = set.size();
string chosen = "";
permutationHelper(m, res, chosen, len);
return res;
}
};
int main() {
string input = "apple";
Solution s;
vector<string> res = s.permutations(input);
for (auto r : res)
std::cout << r << std::endl;
return 0;
}
Mistakes:
1. Loop through map: if only use auto, will only create copies. Thus the function will not recognize changes in map values. So it will treat it like infinite copies of every character, which is not what we want.
2. Use a map to avoid duplications. A problem is how to change duplications in the answer. Note if we only use indices in the original array, it will be hard. Another way is for every result we check if there is already an answer, but this is slow too.
1. Loop through map: if only use auto, will only create copies. Thus the function will not recognize changes in map values. So it will treat it like infinite copies of every character, which is not what we want.
2. Use a map to avoid duplications. A problem is how to change duplications in the answer. Note if we only use indices in the original array, it will be hard. Another way is for every result we check if there is already an answer, but this is slow too.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.