Interview Question
SDE-2sCountry: United States
Solution in python. The cost is the result of multiplying each character of the string by the values that can be replaced for.
def computeCombinations(string, mapping):
values = [ mapping[x] for x in string ]
results = [[]]
for v in values:
results = [x + [y] for x in results
for y in v]
return results
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <stack>
#include <vector>
using namespace std;
map<char, list<char>> str = {
{ '1', { 'a', 'b', 'c', 'd', 'e' } },
{ '2', { 'v', 'w', 'x', 'y', 'z' } }
};
list<string> combs;
void getCombinations(string& currentCombination, string& sub) {
if (sub.empty()) {
combs.push_back(currentCombination);
return;
}
for (auto ch : str[sub[0]]) {
currentCombination.push_back(ch);
getCombinations(currentCombination, sub.substr(1));
currentCombination.pop_back();
}
}
int main()
{
string input = "12212";
string currentCombination;
getCombinations(currentCombination, input);
for (auto combination : combs) {
cout << combination << endl;
}
string line;
cout << "Press enter to close" << endl;
getline(cin, line);
return 0;
}
Hmm. Not that hard. Probably a standard recursive solution would help here, to make it harder and *interview* class:
- NoOne June 11, 2017