网站模板炫酷,中国设计师联盟网站,番禺区网站建设,盘龙区网站建设外包文章目录 摘要描述题解答案题解代码分析统计字符频率判断是否可能构成回文构建半边字符数组回溯生成半边排列 示例测试及结果时间复杂度空间复杂度实际使用场景#xff1a;回文排列在真实项目里能干啥#xff1f;文本处理、数据清洗类系统游戏开发#xff1a;名字合法性验证… 文章目录 摘要描述题解答案题解代码分析统计字符频率判断是否可能构成回文构建半边字符数组回溯生成半边排列 示例测试及结果时间复杂度空间复杂度实际使用场景回文排列在真实项目里能干啥文本处理、数据清洗类系统游戏开发名字合法性验证前端交互与密码强度设计 总结 摘要
本文将深入探讨 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 0var mid var halfChars [Character]()for (char, count) in charCount {if count % 2 ! 0 {oddCount 1mid 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] truebacktrack(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 输入特效、密码提示等
总结
通过统计字符出现次数并判断奇数次出现的字符数量我们可以高效地判断一个字符串的某个排列是否可以构成回文并生成所有可能的回文排列。这个方法简单而有效适用于各种字符串输入。回溯算法在生成排列时注意去重可以避免重复结果。希望本文对你理解回文排列问题有所帮助。
