# Python判断字符串变位词的实现与优化 ## 问题分析 变位词（Anagram）是指由相同字母重新排列形成的不同单词或短语。判断两个字符串是否为变位词是编程中常见的算法问题，需要验证两个字符串是否包含完全相同的字符及其出现次数。 ### 核心逻辑需求 - 字符组成完全相同 - 每个字符的出现次数一致 - 不考虑字符顺序 ## 原始代码问题诊断 ```python n=int(input()) t=1 for i in range(n): a=input() b=input() for x in a: if a.count(x)!=b.count(x): t=0 break if t==1: print("Yes") else : print("No") print('\n') ``` **存在的问题：** | 问题类型 | 具体表现 | 影响 | |---------|---------|------| | 逻辑错误 | 变量`t`未在每次循环重置 | 后续测试结果依赖前次结果 | | 效率低下 | 嵌套循环中使用`count()`方法 | 时间复杂度O(n²) | | 边界处理 | 未考虑字符串长度不同情况 | 可能产生错误判断 | ## 优化方案实现 ### 方案一：使用Python内置Counter类 ```python from collections import Counter def is_anagram_counter(s1: str, s2: str) -> bool: """使用Counter判断是否为变位词""" return Counter(s1) == Counter(s2) # 测试用例 def test_anagram(): n = int(input("请输入测试用例数量: ")) for i in range(n): a = input("请输入第一个字符串: ").strip() b = input("请输入第二个字符串: ").strip() # 使用Counter进行判断 if is_anagram_counter(a, b): print("Yes") else: print("No") test_anagram() ``` **Counter实现优势：** - 时间复杂度：O(n) - 代码简洁易读 - 自动处理字符计数[ref_1] ### 方案二：排序比较法 ```python def is_anagram_sort(s1: str, s2: str) -> bool: """通过排序判断是否为变位词""" # 首先检查长度是否相同 if len(s1) != len(s2): return False # 排序后比较 return sorted(s1) == sorted(s2) # 完整测试程序 def main(): n = int(input("请输入测试用例数量: ")) for i in range(n): str1 = input("输入字符串A: ").strip().lower() # 转为小写处理大小写不敏感 str2 = input("输入字符串B: ").strip().lower() if is_anagram_sort(str1, str2): print("Yes") else: print("No") if __name__ == "__main__": main() ``` ### 方案三：手动字符计数法 ```python def is_anagram_manual(s1: str, s2: str) -> bool: """手动实现字符计数判断变位词""" if len(s1) != len(s2): return False # 创建字符频率字典 char_count = {} # 统计第一个字符串的字符频率 for char in s1: char_count[char] = char_count.get(char, 0) + 1 # 用第二个字符串减少计数 for char in s2: if char not in char_count: return False char_count[char] -= 1 if char_count[char] == 0: del char_count[char] return len(char_count) == 0 # 增强版测试程序 def enhanced_test(): n = int(input("测试用例数量: ")) for i in range(n): a = input("字符串A: ").strip() b = input("字符串B: ").strip() # 提供多种方法验证 result_counter = is_anagram_counter(a, b) result_sort = is_anagram_sort(a, b) result_manual = is_anagram_manual(a, b) # 验证三种方法结果一致性 if result_counter == result_sort == result_manual: print("Yes" if result_counter else "No") else: print("算法验证失败，请检查输入") enhanced_test() ``` ## 性能对比分析 | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | |------|------------|------------|----------| | Counter法 | O(n) | O(k) | 一般情况，代码简洁 | | 排序法 | O(n log n) | O(n) | 需要排序结果的场景 | | 手动计数 | O(n) | O(k) | 理解算法原理，教学用途 | ## 边界情况处理 ```python def robust_anagram_check(s1: str, s2: str, case_sensitive: bool = False) -> bool: """ 健壮的变位词检查函数 参数: s1, s2: 待比较字符串 case_sensitive: 是否区分大小写，默认False 返回: bool: 是否为变位词 """ if not case_sensitive: s1 = s1.lower() s2 = s2.lower() # 移除空格（根据需求） s1 = s1.replace(" ", "") s2 = s2.replace(" ", "") return Counter(s1) == Counter(s2) # 测试边界情况 test_cases = [ ("listen", "silent", True), # 标准变位词 ("Hello", "hello", False), # 大小写敏感 ("aabb", "abab", True), # 重复字符 ("python", "typhon", True), # 实际单词 ("", "", True), # 空字符串 ("a", "a", True), # 单字符 ("abc", "abcd", False), # 长度不同 ] print("边界情况测试结果:") for s1, s2, expected in test_cases: result = robust_anagram_check(s1, s2, case_sensitive=True) status = "✓" if result == expected else "✗" print(f"{status} '{s1}' vs '{s2}': {result} (期望: {expected})") ``` ## 实际应用场景 ### 1. 单词游戏应用 ```python def find_anagrams(word: str, word_list: list) -> list: """在单词列表中查找变位词""" target_sorted = sorted(word.lower()) return [w for w in word_list if sorted(w.lower()) == target_sorted] # 示例：查找"listen"的变位词 word_list = ["silent", "enlist", "listen", "tinsel", "python"] anagrams = find_anagrams("listen", word_list) print(f"'{'listen'}'的变位词: {anagrams}") ``` ### 2. 数据清洗应用 ```python def remove_anagram_duplicates(strings: list) -> list: """移除列表中的变位词重复项""" seen = set() result = [] for s in strings: # 使用排序后的元组作为键 key = tuple(sorted(s.lower())) if key not in seen: seen.add(key) result.append(s) return result # 示例数据清洗 data = ["abc", "bca", "cab", "def", "fed", "xyz"] cleaned = remove_anagram_duplicates(data) print(f"去重后: {cleaned}") ``` ## 总结 通过分析原始代码的问题，我们提供了三种优化方案。**推荐使用Counter方法**，因为它结合了代码简洁性和运行效率。在实际应用中，应根据具体需求选择合适的实现方式，并充分考虑边界情况的处理[ref_2]。对于性能要求极高的场景，手动计数法提供了更好的控制能力，而排序法则在需要排序结果的场景中更为适用。