Medium

题目描述

快乐字符串 是满足以下条件的字符串：

  • 仅包含字母 'a'、'b'、'c'
  • 对于 i 从 1 到 s.length - 1 的所有值，都有 s[i] != s[i + 1]（字符串的索引从 1 开始）

例如，字符串 "abc"、"ac"、"b" 和 "abcbabcbcb" 都是快乐字符串，而 "aa"、"baa" 和 "ababbc" 都不是快乐字符串。

给你两个整数 n 和 k，你需要将长度为 n 的所有快乐字符串按字典序排序。

请返回排序后的第 k 个快乐字符串，如果长度为 n 的快乐字符串少于 k 个，那么请返回 空字符串。

示例 1：

输入：n = 1, k = 3
输出："c"
解释：列表 ["a", "b", "c"] 包含了所有长度为 1 的快乐字符串。第三个字符串是 "c"。

示例 2：

输入：n = 1, k = 4
输出：""
解释：长度为 1 的快乐字符串只有 3 个。

示例 3：

输入：n = 3, k = 9
输出："cab"
解释：长度为 3 的快乐字符串有 12 个 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]。第 9 个字符串是 "cab"。

提示：

  • 1 <= n <= 10
  • 1 <= k <= 100

解题思路

这道题可以用两种方法解决：回溯生成所有字符串 和 数学计算直接构造。

方法一：回溯生成（简单直观）

由于约束条件较小（n ≤ 10），我们可以用回溯法生成所有可能的快乐字符串，然后按字典序排序，取第 k 个。

回溯过程：

  • 第一位可以选择 ‘a’、‘b’、‘c’ 任意一个
  • 后续位置只能选择与前一位不同的两个字符
  • 生成所有长度为 n 的字符串后排序

方法二：数学计算（推荐）

分析规律：

  • 第一位有 3 种选择：‘a’、‘b’、‘c’
  • 第二位及之后每位都有 2 种选择（不能与前一位相同）
  • 总共有 3 × 2^(n-1) 个快乐字符串

我们可以通过数学计算直接确定第 k 个字符串的每一位：

  1. 计算每个首字母开头的字符串数量：2^(n-1)
  2. 根据 k 值确定首字母
  3. 递归计算后续每一位

这种方法时间复杂度更低，空间复杂度也更小。

代码实现

class Solution {
public:
    string getHappyString(int n, int k) {
        // 计算总的快乐字符串数量
        int total = 3;
        for (int i = 1; i < n; i++) {
            total *= 2;
        }
        
        if (k > total) return "";
        
        string result = "";
        vector<char> chars = {'a', 'b', 'c'};
        k--; // 转换为0-indexed
        
        // 确定第一个字符
        int groupSize = total / 3;
        int firstCharIndex = k / groupSize;
        result += chars[firstCharIndex];
        k %= groupSize;
        
        // 确定后续字符
        for (int i = 1; i < n; i++) {
            vector<char> available;
            for (char c : chars) {
                if (c != result.back()) {
                    available.push_back(c);
                }
            }
            
            groupSize /= 2;
            int charIndex = k / groupSize;
            result += available[charIndex];
            k %= groupSize;
        }
        
        return result;
    }
};

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        # 计算总的快乐字符串数量
        total = 3 * (2 ** (n - 1))
        
        if k > total:
            return ""
        
        chars = ['a', 'b', 'c']
        result = []
        k -= 1  # 转换为0-indexed
        
        # 确定第一个字符
        group_size = total // 3
        first_char_index = k // group_size
        result.append(chars[first_char_index])
        k %= group_size
        
        # 确定后续字符
        for i in range(1, n):
            available = [c for c in chars if c != result[-1]]
            group_size //= 2
            char_index = k // group_size
            result.append(available[char_index])
            k %= group_size
        
        return ''.join(result)

public class Solution {
    public string GetHappyString(int n, int k) {
        // 计算总的快乐字符串数量
        int total = 3;
        for (int i = 1; i < n; i++) {
            total *= 2;
        }
        
        if (k > total) return "";
        
        char[] chars = {'a', 'b', 'c'};
        StringBuilder result = new StringBuilder();
        k--; // 转换为0-indexed
        
        // 确定第一个字符
        int groupSize = total / 3;
        int firstCharIndex = k / groupSize;
        result.Append(chars[firstCharIndex]);
        k %= groupSize;
        
        // 确定后续字符
        for (int i = 1; i < n; i++) {
            List<char> available = new List<char>();
            foreach (char c in chars) {
                if (c != result[result.Length - 1]) {
                    available.Add(c);
                }
            }
            
            groupSize /= 2;
            int charIndex = k / groupSize;
            result.Append(available[charIndex]);
            k %= groupSize;
        }
        
        return result.ToString();
    }
}

var getHappyString = function(n, k) {
    // 计算总的快乐字符串数量
    let total = 3;
    for (let i = 1; i < n; i++) {
        total *= 2;
    }
    
    if (k > total) return "";
    
    const chars = ['a', 'b', 'c'];
    let result = "";
    k--; // 转换为0-indexed
    
    // 确定第一个字符
    let groupSize = Math.floor(total / 3);
    const firstCharIndex = Math.floor(k / groupSize);
    result += chars[firstCharIndex];
    k %= groupSize;
    
    // 确定后续字符
    for (let i = 1; i < n; i++) {
        const available = chars.filter(c => c !== result[result.length - 1]);
        groupSize = Math.floor(groupSize / 2);
        const charIndex = Math.floor(k / groupSize);
        result += available[charIndex];
        k %= groupSize;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数学计算方法回溯生成方法
时间复杂度O(n)O(3 × 2^(n-1) × log(3 × 2^(n-1)))
空间复杂度O(1)O(3 × 2^(n-1))

推荐使用数学计算方法，因为它在时间和空间复杂度上都有显著优势。