长度为 n 的开心符串中字典序第 k 小的字符串1

题目描述

题目讲解

广度优先搜索(BFS)与深度优先搜索(DFS)比较

广度优先搜索 深度优先搜索
天然保持字典序,直接数第k个即可 生成所有结果后再排序，才能保证字典序

具体流程

  • 使用n = 3, k = 4 的例子, 采用广度优先搜索 讲解

代码

广度优先搜索
深度优先搜索
class Solution:
  def getHappyString(self, n:int, k:int)->str:
    from collections import deque
    next_letters = ['a': "bc", 'b':"ac", 'c':"ab"]
    q = deque(["a", "b", "c"])
    while len(q[0]) != n:
      u = q.popleft()
      for ch in next_letters[u[-1]]:
        q.append(u+ch)
    if len(q) < k:
      return ""
    for _ in range(k - 1):
      q.popleft()
    return q[0]

class Solution:
  def getHappyString(self, n:int, k:int)->str:
    res = []
    def dfs(path):
      if len(path) == n:
        res.append(path)
        return
    for ch in "abc"
      if not path or path[-1] != ch:
        dfs(path + ch)
  dfs("")
  res.sort()
  return res[k-1] if k <= len(res) else ""

链接

  1. 长度为 n 的开心符串中字典序第 k 小的字符串https://leetcode.cn/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/description/ ↩︎