kth-smallest-instructions

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Bob is standing at cell <code>(0, 0)</code>, and he wants to reach <code>destination</code>: <code>(row, column)</code>. He can only travel right and down. You are going to help Bob by providing instructions for him to reach <code>destination</code>.

The instructions are represented as a string, where each character is either:

<ul>
	<li><code>&#39;H&#39;</code>, meaning move horizontally (go right), or</li>
	<li><code>&#39;V&#39;</code>, meaning move vertically (go down).</li>
</ul>

Multiple instructions will lead Bob to <code>destination</code>. For example, if <code>destination</code> is <code>(2, 3)</code>, both <code>&quot;HHHVV&quot;</code> and <code>&quot;HVHVH&quot;</code> are valid instructions.

However, Bob is very picky. Bob has a lucky number <code>k</code>, and he wants the <code>kth</code> lexicographically smallest instructions that will lead him to <code>destination</code>. <code>k</code> is 1-indexed.

Given an integer array <code>destination</code> and an integer <code>k</code>, return the <code>kth</code> lexicographically smallest instructions that will take Bob to <code>destination</code>.

&nbsp;
Example 1:

<img alt="" src="https://assets.leetcode.com/uploads/2020/10/12/ex1.png" style="width: 300px; height: 229px;" />

<pre>
Input: destination = [2,3], k = 1
Output: &quot;HHHVV&quot;
Explanation: All the instructions that reach (2, 3) in lexicographic order are as follows:
[&quot;HHHVV&quot;, &quot;HHVHV&quot;, &quot;HHVVH&quot;, &quot;HVHHV&quot;, &quot;HVHVH&quot;, &quot;HVVHH&quot;, &quot;VHHHV&quot;, &quot;VHHVH&quot;, &quot;VHVHH&quot;, &quot;VVHHH&quot;].
</pre>

Example 2:

<img alt="" src="https://assets.leetcode.com/uploads/2020/10/12/ex2.png" style="width: 300px; height: 229px;" />

<pre>
Input: destination = [2,3], k = 2
Output: &quot;HHVHV&quot;
</pre>

Example 3:

<img alt="" src="https://assets.leetcode.com/uploads/2020/10/12/ex3.png" style="width: 300px; height: 229px;" />

<pre>
Input: destination = [2,3], k = 3
Output: &quot;HHVVH&quot;
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>destination.length == 2</code></li>
	<li><code>1 &lt;= row, column &lt;= 15</code></li>
	<li><code>1 &lt;= k &lt;= nCr(row + column, row)</code>, where <code>nCr(a, b)</code> denotes <code>a</code> choose <code>b</code>​​​​​.</li>
</ul>

kthSmallestPath

Kth Smallest Instructions

Array

Math

Dynamic Programming

Combinatorics

Bob 站在单元格 <code>(0, 0)</code> ，想要前往目的地 <code>destination</code> ：<code>(row, column)</code> 。他只能向 右 或向 下 走。你可以为 Bob 提供导航 指令 来帮助他到达目的地 <code>destination</code> 。

指令 用字符串表示，其中每个字符：

<ul>
	<li><code>'H'</code> ，意味着水平向右移动</li>
	<li><code>'V'</code> ，意味着竖直向下移动</li>
</ul>

能够为 Bob 导航到目的地 <code>destination</code> 的指令可以有多种，例如，如果目的地 <code>destination</code> 是 <code>(2, 3)</code>，<code>"HHHVV"</code> 和 <code>"HVHVH"</code> 都是有效 指令 。

<ul>
</ul>

然而，Bob 很挑剔。因为他的幸运数字是 <code>k</code>，他想要遵循 按字典序排列后的第 <code>k</code> 条最小指令 的导航前往目的地 <code>destination</code> 。<code>k</code>  的编号 从 1 开始 。

给你一个整数数组 <code>destination</code> 和一个整数 <code>k</code> ，请你返回可以为 Bob 提供前往目的地 <code>destination</code> 导航的 按字典序排列后的第 <code>k</code> 条最小指令 。

 

示例 1：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/01/ex1.png" style="width: 300px;" />

<pre>
输入：destination = [2,3], k = 1
输出："HHHVV"
解释：能前往 (2, 3) 的所有导航指令 按字典序排列后 如下所示：
["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].
</pre>

示例 2：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/01/ex2.png" style="width: 300px; height: 229px;" />

<pre>
输入：destination = [2,3], k = 2
输出："HHVHV"
</pre>

示例 3：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/01/ex3.png" style="width: 300px; height: 229px;" />

<pre>
输入：destination = [2,3], k = 3
输出："HHVVH"
</pre>

 

提示：

<ul>
	<li><code>destination.length == 2</code></li>
	<li><code>1 <= row, column <= 15</code></li>
	<li><code>1 <= k <= nCr(row + column, row)</code>，其中 <code>nCr(a, b)</code> 表示组合数，即从 <code>a</code> 个物品中选 <code>b</code> 个物品的不同方案数。</li>
</ul>