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

这道题到底在问什么

输入

n = 1, k = 3

输出

"c" (a, b, c 三个里第 3 个)

输入

n = 3, k = 9

输出

"cab"

输入

n = 2, k = 7

输出

"" (长度 2 只有 6 个, 第 7 个不存在)

最优解：一步一步想明白

1. 3记牢两句:按 a b c 顺序放、避开和前一位相同的字母,收集顺序天然是字典序;凑够 k 个立刻刹车。下面每一帧都在套它。
2. 4先看画面。上面这排 a、b、c 是每一位能用的三个字母,谁和前一位重复就在它上面打叉、本位不能选。中间 path 是正在拼的串,从空开始一位一位往后接。右边结果区按字典序收集已经拼好的开心串。我们从最小的字母开头往下搜,收集到第 9 个就停。
3. 5第 1 位起手。前面没有字符,a、b、c 都能放,按字典序先挑最小的 a。path 现在是 a。
4. 6到第 2 位。前一位是 a,再放 a 就相邻重复了,给 a 打叉跳过。下一个最小的是 b,和 a 不同,放下,path 成了 ab。
5. 7第 3 位,前一位是 b,b 打叉不能用。按字典序最小的 a 和 b 不同,放 a。三位拼满,凑出 aba,这是收集到的第 1 个开心字符串,收进结果区。
6. 8退回第 3 位换下一个。a 试过了,b 又和前一位重复,于是落到 c。拼成 abc,第 2 个,收下。
7. 9第 2 位是 b 的两支搜完了,退回第 2 位。a 和前一位重复要打叉,b 刚搜过,这次轮到 c,path 变成 ac。
8. 10第 3 位前一位是 c,c 打叉。最小的 a 可以放,拼出 aca,第 3 个。
9. 11再退回换下一个,a 用过、c 重复,放 b,得到 acb,第 4 个。a 打头的四个开心串到齐了。
10. 12a 当第 1 位的分支全部走完,依次收了 aba、abc、aca、acb 四个。把 path 一路退回空,回到第 1 位换下一个字母。
11. 13第 1 位这次放 b,重新往后搜。
12. 14第 2 位前一位是 b,b 打叉,最小的 a 和它不同,放 a,path 是 ba。
13. 15第 3 位前一位是 a,a 跳过,放 b,拼成 bab,第 5 个。
14. 16退回换下一个,b 用过,放 c,得到 bac,第 6 个。
15. 17退回第 2 位,a 这支搜完、b 和前一位重复,换 c,path 成了 bc。
16. 18第 3 位前一位是 c,放最小的 a,拼出 bca,第 7 个。
17. 19再换下一个,a 用过、c 重复,放 b,得到 bcb,第 8 个。b 打头的四个也凑齐了。
18. 20b 当第 1 位的分支也清完,又收了四个,现在一共 8 个。退回空 path,第 1 位换最后一个字母 c。
19. 21第 1 位放 c。我们只差第 9 个了,盯紧这一支。
20. 22第 2 位前一位是 c,c 打叉,放最小的 a,path 是 ca。
21. 23第 3 位前一位是 a,a 跳过,放 b,拼成 cab。这正好是收集到的第 9 个,也就是要找的答案。一凑够 9 个就立刻刹车,后面的串不用再生成。
22. 24回头看结果区,按字典序排好的开心串依次是 aba、abc、aca、acb、bab、bac、bca、bcb、cab,第 9 个正是 cab,把它返回就是答案。跟开头说的对上了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        def dfs():
            if len(ans) >= k:
                return
            if len(s) == n:
                ans.append("".join(s))
                return
            for c in "abc":
                if not s or s[-1] != c:
                    s.append(c)
                    dfs()
                    s.pop()

        ans = []
        s = []
        dfs()
        return "" if len(ans) < k else ans[k - 1]

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    string getHappyString(int n, int k) {
        vector<string> ans;
        string s = "";
        function<void()> dfs = [&](  ) -> void {
            if (ans.size() >= k) {
                return;
            }
            if (s.size() == n) {
                ans.emplace_back(s);
                return;
            }
            for (char c = 'a'; c <= 'c'; ++c) {
                if (s.empty() || s.back() != c) {
                    s.push_back(c);
                    dfs();
                    s.pop_back();
                }
            }
        };
        dfs();
        return ans.size() < k ? "" : ans[k - 1];
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private List<String> ans = new ArrayList<>();
    private StringBuilder s = new StringBuilder();
    private int n, k;

    public String getHappyString(int n, int k) {
        this.n = n;
        this.k = k;
        dfs();
        return ans.size() < k ? "" : ans.get(k - 1);
    }

    private void dfs() {
        if (ans.size() >= k) {
            return;
        }
        if (s.length() == n) {
            ans.add(s.toString());
            return;
        }
        for (char c : "abc".toCharArray()) {
            if (s.length() == 0 || s.charAt(s.length() - 1) != c) {
                s.append(c);
                dfs();
                s.deleteCharAt(s.length() - 1);
            }
        }
    }
}

复杂度

面试官可能追问