I have an online assessment for which I have 8 days remaining to complete. The assessment is about moving through a grid. Essentially, you need to compute permutations of strings containing some set number of 'H's and 'V's (for horizontal and vertical). And then return the "ith" permutation. Problem is called gridworld.
I've tried several solutions using Java and C++ that compute the permutations. They work, but keep exceeding time limit for about half the test cases.
I'm wondering if there's a way to directly compute the "ith" permutation of a string containing some number of 'H's and 'V's? The idea is to compute the strings in lexicographic order, and then return the ith permutation. thanks!
My solution
static vector<string> resultList;
static int counter;
void permutations(int currH, int currV, int maxH, int maxV, string nextPerm, int i, int key);
vector<string> getSafePaths(vector<string> journeys) {
vector<string> returnList;
for (int i = 0; i < journeys.size(); i++){
resultList.clear();
counter = 0;
stringstream stream(journeys[i]);
int nextX;
stream >> nextX;
//cout << nextX;
int nextY;
stream >> nextY;
//cout << nextY;
int nextKey;
stream >> nextKey;
//cout << nextKey;
string next = "";
permutations(0, 0, nextX, nextY, next, 0, nextKey);
string retVal = resultList[nextKey];
returnList.push_back(retVal);
}
//vector<string> vect =;
return returnList;
}
void permutations(int currH, int currV, int maxH, int maxV, string nextPerm, int i, int key){
if (i == maxH + maxV){
counter++;
resultList.push_back(nextPerm);
// cout << nextPerm << endl;
return;
}
if (currH < maxH){
//if (nextPerm.size() > i && nextPerm.at(i) =='V'){
// currV--;
// }
currH++;
string next;
next.assign(nextPerm);
next.push_back('H');
permutations(currH, currV, maxH, maxV, next, i + 1, key);
if (counter > key){
return;
}
currH--;
}
if (currV < maxV){
// if (nextPerm.size() > i && nextPerm.at(i) == 'H'){
// currH--;
// }
currV++;
string next;
next.assign(nextPerm);
next.push_back('V');
permutations(currH, currV, maxH, maxV,next, i + 1, key);
}
}Comments (15)
