LeetCode 267：回文排列 II —— Swift 解法全解析-EW帮帮网

在这里插入图片描述

文章目录

摘要

本文将深入探讨 LeetCode 第 267 题 —— 回文排列 II。我们将提供 Swift 的解题方案，解析其背后的逻辑，并通过示例测试验证其正确性。通过本篇文章，你将了解如何判断一个字符串的某个排列是否可以构成回文，并生成所有可能的回文排列。

描述

给定一个字符串 s，返回所有可能的回文排列（不重复）。如果无法构成回文，返回空列表。

示例 1：

输入: "aabb"
输出: ["abba", "baab"]

示例 2：

输入: "abc"
输出: []

提示：

字符串长度范围：1 <= s.length <= 16
字符串仅包含小写英文字母

题解答案

func generatePalindromes(_ s: String) -> [String] {
    var charCount = [Character: Int]()
    for char in s {
        charCount[char, default: 0] += 1
    }

    var oddCount = 0
    var mid = ""
    var halfChars = [Character]()
    for (char, count) in charCount {
        if count % 2 != 0 {
            oddCount += 1
            mid = String(char)
        }
        halfChars += Array(repeating: char, count: count / 2)
    }

    if oddCount > 1 {
        return []
    }

    var results = [String]()
    var used = [Bool](repeating: false, count: halfChars.count)
    halfChars.sort()
    backtrack(&halfChars, &used, "", mid, &results)
    return results
}

func backtrack(_ halfChars: inout [Character], _ used: inout [Bool], _ path: String, _ mid: String, _ results: inout [String]) {
    if path.count == halfChars.count {
        let reversed = String(path.reversed())
        results.append(path + mid + reversed)
        return
    }

    for i in 0..<halfChars.count {
        if used[i] {
            continue
        }
        if i > 0 && halfChars[i] == halfChars[i - 1] && !used[i - 1] {
            continue
        }
        used[i] = true
        backtrack(&halfChars, &used, path + String(halfChars[i]), mid, &results)
        used[i] = false
    }
}

题解代码分析

统计字符频率

我们首先统计字符串中每个字符出现的次数。通过遍历字符串，将每个字符的出现次数记录在字典 charCount 中。

判断是否可能构成回文

回文字符串的特点是：除了最多一个字符可以出现奇数次，其他字符必须出现偶数次。因此，我们统计出现奇数次的字符数量 oddCount。如果 oddCount 大于 1，则无法构成回文，直接返回空列表。

同时，我们记录出现奇数次的字符 mid，它将位于回文字符串的中间位置。

构建半边字符数组

对于每个字符，将其出现次数除以 2，得到一半的字符数组 halfChars。这是因为回文字符串是对称的，我们只需要生成一半的排列，另一半是其镜像。

回溯生成半边排列

我们使用回溯算法生成 halfChars 的所有不重复排列。为了避免重复，我们先对 halfChars 进行排序，并在回溯过程中跳过重复的字符。

在回溯的每一步，我们将当前路径 path 与其反转字符串 reversed 以及中间字符 mid 组合，构成一个完整的回文字符串，并添加到结果列表 results 中。

示例测试及结果

print(generatePalindromes("aabb"))  // 输出: ["abba", "baab"]
print(generatePalindromes("abc"))   // 输出: []
print(generatePalindromes("aabbh")) // 输出: ["abhha", "bahhb"]

这些测试用例验证了我们的算法在不同输入下的正确性。

时间复杂度

时间复杂度：O(n!)，其中 n 是字符串的长度。由于需要生成所有可能的排列，最坏情况下时间复杂度为阶乘级别。

空间复杂度

空间复杂度：O(n)，主要用于存储字符频率的字典、半边字符数组以及递归调用的栈空间。

当然可以，以下是加入了实际日常使用场景的优化版内容：

实际使用场景：回文排列在真实项目里能干啥？

乍一看，“生成回文字符串的所有排列”像是个纯算法题，没啥工程价值。但实际上，这种“回文判断 + 组合生成” 的能力在很多实际业务中也能派上用场，下面举几个接地气的例子：

文本处理、数据清洗类系统

假设你在做一个 聊天记录分析系统，需要识别用户是否输入了恶搞或特定格式的文本，比如“我叫ABBA，我的狗叫OTTO”，这种是典型的回文。

通过这个算法，你可以：

快速识别是否可能是“对称型伪指令”
标记为潜在的彩蛋、反转词分析
做 NLP 模型数据增强时制造对称样本

游戏开发：名字合法性验证

在一些游戏中，玩家喜欢起一些特殊格式的名字，比如：

“雷神之心🪙nihs之神雷”
“回文杀abccba”

你可以通过这个算法辅助判断：当前玩家输入的名字是不是某种“可回文组合”，来判断是否触发某些特效或彩蛋。

前端交互与密码强度设计

有些前端 UI 组件里需要检查用户输入内容是否有模式化特征。比如：

检查用户密码是不是“123321”、“abcba”这种对称字符串，降低安全评分；
在输入文本时检测是否构成了一个回文并弹出动画（比如 AI 输入特效、密码提示等）

总结

通过统计字符出现次数并判断奇数次出现的字符数量，我们可以高效地判断一个字符串的某个排列是否可以构成回文，并生成所有可能的回文排列。这个方法简单而有效，适用于各种字符串输入。回溯算法在生成排列时，注意去重可以避免重复结果。希望本文对你理解回文排列问题有所帮助。

LeetCode 267：回文排列 II —— Swift 解法全解析