Python程序：查找字典序第k小的n长度字符串

假设我们有一个数字n和另一个值k。现在让我们考虑一个仅包含“0”，“1”和“2”的字符串，其中没有字符连续重复。我们必须选择长度为n的此类字符串并找到字典序第k小的字符串。如果没有第k个字符串，则返回空字符串。

因此，如果输入类似于n = 4 k = 2，则输出将为“0120”。

为了解决这个问题，我们将遵循以下步骤

• 定义一个方法solve()，它将接收s、k和last
• 如果s等于0，则
  • 返回空字符串
• 对于“012”中的每个字符c，执行以下操作
  • 如果c等于last，则
    • 进行下一次迭代
  • 如果k < 2^(s-1)，则
    • 返回c + solve(s - 1, k, c)
  • k := k - 2^(s-1)
• 返回空字符串
• 从主方法调用solve(n, k, Null)

让我们查看以下实现以获得更好的理解

示例代码

在线演示

class Solution:
   def solve(self, s, k, last=None):
      if s == 0:
         return ""
         for c in "012":
            if c == last:
               continue
            if k < 2 ** (s - 1):
               return c + self.solve(s - 1, k, c)
            k -= 2 ** (s - 1)
         return ""

ob = Solution()
n = 4
k = 2
print(ob.solve(n, k))

输入

4, 2

输出

0120

Arnab Chakraborty

更新于: 2020年11月25日

457 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始