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

力扣1415. 长度为 n 的开心字符串中字典序第 k 小的字符串

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        """
        获取第 k 个长度为 n 的快乐字符串
        
        快乐字符串定义：只包含字母 'a'、'b'、'c'，且相邻字符不相同的字符串
        
        Args:
            n (int): 目标字符串的长度
            k (int): 要返回的第 k 个字符串（按字典序）
        
        Returns:
            str: 第 k 个快乐字符串，如果不存在则返回空字符串
        """
        ans = []

        def dfs(s):
            """
            深度优先搜索生成所有快乐字符串
            
            Args:
                s (str): 当前已构建的字符串
            """
            if len(s) == n:
                # 字符串长度达到 n 加入结果集
                ans.append(s)
                return
            for x in ["a", "b", "c"]:
                if s != '' and s[-1] == x:
                    # 跳过与前一个字符相同的字符
                    continue
                dfs(s + x)
        
        dfs('')
        ans.sort()
        return ans[k - 1] if len(ans) >= k else ''