Description#
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:
![](https://spcdn.pages.dev/leetcode/problems/1643.Kth%20Smallest%20Instructions/images/ex1.png)
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"].
Example 2:
![](https://spcdn.pages.dev/leetcode/problems/1643.Kth%20Smallest%20Instructions/images/ex2.png)
Input: destination = [2,3], k = 2
Output: "HHVHV"
Example 3:
![](https://spcdn.pages.dev/leetcode/problems/1643.Kth%20Smallest%20Instructions/images/ex3.png)
Input: destination = [2,3], k = 3
Output: "HHVVH"
Constraints:
destination.length == 2
1 <= row, column <= 15
1 <= k <= nCr(row + column, row)
, where nCr(a, b)
denotes a
choose b
.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def kthSmallestPath(self, destination: List[int], k: int) -> str:
v, h = destination
ans = []
for _ in range(h + v):
if h == 0:
ans.append("V")
else:
x = comb(h + v - 1, h - 1)
if k > x:
ans.append("V")
v -= 1
k -= x
else:
ans.append("H")
h -= 1
return "".join(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public String kthSmallestPath(int[] destination, int k) {
int v = destination[0], h = destination[1];
int n = v + h;
int[][] c = new int[n + 1][h + 1];
c[0][0] = 1;
for (int i = 1; i <= n; ++i) {
c[i][0] = 1;
for (int j = 1; j <= h; ++j) {
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
StringBuilder ans = new StringBuilder();
for (int i = n; i > 0; --i) {
if (h == 0) {
ans.append('V');
} else {
int x = c[v + h - 1][h - 1];
if (k > x) {
ans.append('V');
k -= x;
--v;
} else {
ans.append('H');
--h;
}
}
}
return ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
string kthSmallestPath(vector<int>& destination, int k) {
int v = destination[0], h = destination[1];
int n = v + h;
int c[n + 1][h + 1];
memset(c, 0, sizeof(c));
c[0][0] = 1;
for (int i = 1; i <= n; ++i) {
c[i][0] = 1;
for (int j = 1; j <= h; ++j) {
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
string ans;
for (int i = 0; i < n; ++i) {
if (h == 0) {
ans.push_back('V');
} else {
int x = c[v + h - 1][h - 1];
if (k > x) {
ans.push_back('V');
--v;
k -= x;
} else {
ans.push_back('H');
--h;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| func kthSmallestPath(destination []int, k int) string {
v, h := destination[0], destination[1]
n := v + h
c := make([][]int, n+1)
for i := range c {
c[i] = make([]int, h+1)
c[i][0] = 1
}
for i := 1; i <= n; i++ {
for j := 1; j <= h; j++ {
c[i][j] = c[i-1][j] + c[i-1][j-1]
}
}
ans := []byte{}
for i := 0; i < n; i++ {
if h == 0 {
ans = append(ans, 'V')
} else {
x := c[v+h-1][h-1]
if k > x {
ans = append(ans, 'V')
k -= x
v--
} else {
ans = append(ans, 'H')
h--
}
}
}
return string(ans)
}
|