Hi I participated in Leetcode weekly contest 213 and am facing issue with submission for below question Kth Smallest Instructions
Bob is standing at cell (0, 0), and he wants to reach destination: (row, column). He can only travel right and down. You are going to help Bob by providing instructions for him to reach destination.
The instructions are represented as a string, where each character is either:
'H', meaning move horizontally (go right), or 'V', meaning move vertically (go down). Multiple instructions will lead Bob to destination. For example, if destination is (2, 3), both "HHHVV" and "HVHVH" are valid instructions.
However, Bob is very picky. Bob has a lucky number k, and he wants the kth lexicographically smallest instructions that will lead him to destination. k is 1-indexed.
Given an integer array destination and an integer k, return the kth lexicographically smallest instructions that will take Bob to destination.
Example 1 :
Input: destination = [2,3], k = 1
Output: "HHHVV"
Explanation: All the instructions that reach (2, 3) in lexicographic order are as follows: ["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].Constraints:
destination.length == 2
1 <= row, column <= 15
1 <= k <= nCr(row + column, row), where nCr(a, b) denotes a choose b.
I tried to create all the possible paths lexicographically and stop when count reached k, but it giving me TLE.
Below is my code :
public class Solution {
String res = string.Empty;
int count = 0;
int K;
public string KthSmallestPath(int[] destination, int k) {
K=k;
this.FindAllPaths("", destination[1], destination[0]);
return res;
}
public void FindAllPaths(string currPath, int hRem, int vRem)
{
if(count == K) return;
if(hRem == 0 && vRem == 0)
{
res = currPath;
count++;
return;
}
if(hRem != 0)
{
this.FindAllPaths(currPath + 'H', hRem - 1, vRem);
}
if(vRem != 0)
{
this.FindAllPaths(currPath + 'V', hRem, vRem - 1);
}
}
}
Any idea on how can I optimize the code so that it passes all the test cases.