1643. Kth Smallest Instructions

https://leetcode.com/problems/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"].

Example 2:

Input: destination = [2,3], k = 2
Output: "HHVHV"

Example 3:

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​​​​​.

从格子(0,0)可向下或向右走到(v,h)处，向下的指令V，向右指令为H，问所有指令序列中字典序排第K小的。无论怎么走最后都需要v个V和h个H，而当字符串中每一种字符的数量固定时，求字典序第 k 小的字符串，可以从高位向低位依次确定每一个位置的字符。当在最高位放置V，那所有最高位为 H 的字符串的字典序都比它小，这样的字符串共有comb(h + v - 1, h - 1)个，即剩余 h+v-1个位置中选择 h-1个放入 H，其余位置自动放入 V方案数。因此如果 k大于这个组合数，那么最高位一定是V，v--，k -= comb；如果 k小，最高位是H, h-=1，但不需要改变 k 的值，因为剩余部分就是包含 (h-1,v)的字典序第 k 小的字符串。

参考自zerotrac2。

from math import comb

class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        v, h = destination
        res = []
        for _ in range(h + v):
            if h == 0:
                res.append('V')
                v -= 1
                continue
            elif v == 0:
                res.append('H')
                h -= 1
                continue
            c = comb(h + v - 1, h - 1)
            if k > c:
                res.append('V')
                v -= 1
                k -= c
            else:
                res.append('H')
                h -= 1
        return ''.join(res)