Kth Smallest Instructions LeetCode solution in Python

1
from math import comb
2

3

4
class Solution:
5
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
6
        i, j = destination
7

8
        @lru_cache(None)
9
        def helper(i, j, k):
10
            if k == 1:
11
                return "H" * j + "V" * i
12
            else:
13
                horizontal = comb(i + j - 1, j - 1)
14
                if k <= horizontal:
15
                    return "H" + helper(i, j - 1, k)
16
                else:
17
                    return "V" + helper(i - 1, j, k - horizontal)
18

19
        return helper(i, j, k)