一、什么是变位词？

指两个词之间存在组成字母的重新排列关系，则认为是变位词；

比如 “weixin” 和 “xinwei” 这两个词所使用的字母完全一样，因此是变位词。

二、问题提出

所谓“变位词”是指两个词之间存在组成字母的重新排列关系

如 heart和 earth，python和 typhon

为了简单起见，假设参与判断的两个词仅由小写字母组成，而且长度相等

解题目标：写一个bool函数，以两个词作为参数，返回这两个词是否为变位词

三、问题解决

1、使用字符计数数组，通过加、减操作来统计和比较字符频率

def word_search(word1: str, word2: str) -> bool:
    char_count = [0] * 26  # 存储每个字符出现的次数
    for i in word1:
        char_count[ord(i) - ord('a')] += 1  # 计算 word1 中字符的出现次数
    for i in word2:
        index = ord(i) - ord('a')
        char_count[index] -= 1  # 减去 word2 中字符的出现次数
        if char_count[index] < 0:  # 如果出现次数为负，说明 word2 中该字符过多
            return False
    for count in char_count:  # 检查是否所有字符的出现次数都为 0
        if count != 0:
            return False
    return True

方法：

• 首先，创建一个长度为 26 的列表 char_count 来存储每个小写字母出现的次数，初始值都为 0。如果26个字母出现的次数相同，那么一定是个变位词。

• 遍历 word1 中的每个字符，将其出现次数累加到 char_count 中对应的位置（通过 ord(i) - ord('a') 计算字符的索引）。
• 接着遍历 word2 中的每个字符，将其出现次数从 char_count 中对应的位置减去。
• 如果在减去 word2 中字符的出现次数时，发现该位置的计数值小于 0，则说明 word2 中该字符出现的次数多于 word1，直接返回 False。
• 最后，再次遍历 char_count，如果存在不为 0 的元素，说明两个单词中字符出现的频率不一致，返回 False；如果都为 0，则认为它们是变位词，返回 True。

解释：

• 该方法通过统计两个单词中每个字符的出现次数来判断是否为变位词。将 word1 中字符出现次数加 1，将 word2 中字符出现次数减 1，如果最终每个字符的计数都为 0，则说明两个单词包含相同的字符且每个字符的出现次数相同，即为变位词。

时间复杂度：

• 时间复杂度为
  O(n)

注意点(ord关键字)：

• ord() 是 Python 的内置函数，它接受一个长度为 1 的字符串（即一个字符）作为输入，并返回该字符的 Unicode 码点。
• 使用场景：
  • 字符比较：可以用于比较字符的顺序，因为 Unicode 码点为字符提供了一个数字表示，方便进行大小比较。

2、使用 Counter 类

def search_demo2(word1: str, word2: str) -> bool:
    return Counter(word1) == Counter(word2)

方法：

• 使用 Counter 类（需从 collections 模块导入），它会统计字符串中每个字符的出现次数并存储为一个字典，其中键是字符，值是出现次数。
• 比较 word1 和 word2 的 Counter 对象是否相等，如果相等，则认为它们是变位词，返回 True；否则返回 False。

解释：

• 该方法利用 Counter 类的特性，自动统计并存储每个字符的出现次数，然后直接比较两个单词的字符频率统计结果是否完全相同，相同则为变位词。

时间复杂度：

• 时间复杂度为
  O(n)

3、使用嵌套循环和标记法

def anagram_solution(s1, s2):
    if len(s1) == len(s2):
        alist = list(s2)
        pos1 = 0
        stillOK = True
        while pos1 < len(s1) and stillOK:
            pos2 = 0
            found = False
            while pos2 < len(alist) and not found:
                if s1[pos1] == alist[pos2]:
                    found = True
                else:
                    pos2 = pos2 + 1
            if found:
                alist[pos2] = None
            else:
                stillOK = False
            pos1 = pos1 + 1
        return stillOK
    else:
        return False

方法：

• 首先，检查 s1 和 s2 的长度是否相等，如果不相等，直接返回 False。
• 将 s2 转换为列表 alist。
• 初始化 pos1 为 0 和 stillOK 为 True。
• 外层 while 循环遍历 s1 的每个位置，内层 while 循环在 alist 中查找 s1[pos1] 出现的位置。
• 若找到，将 alist 中该位置置为 None，表示已匹配；若未找到，将 stillOK 设为 False，表示不是变位词。

解释：

• 此方法通过遍历 s1 中的每个字符，在 s2 列表中寻找相同字符，找到一个匹配后将其标记为 None，若最终都能找到匹配，且 s1 和 s2 长度相同，则认为是变位词；否则不是。

时间复杂度：

• 时间复杂度为

  O(n^{2})

  时间复杂度较高

4、使用排序和比较

def anagram_solution2(s1, s2):
    if len(s1) != len(s2):  # 先比较长度，如果长度不同直接返回 False
        return False
    alist1 = list(s1)
    alist2 = list(s2)
    alist1.sort()
    alist2.sort()
    pos = 0
    matches = True
    while pos < len(s1) and matches:
        if alist1[pos] == alist2[pos]:
            pos = pos + 1
        else:
            matches = False
    return matches

方法：

• 首先检查 s1 和 s2 的长度是否相等，如果不相等，直接返回 False。
• 将 s1 和 s2 分别转换为列表 alist1 和 alist2，并对它们进行排序。
• 初始化 pos 为 0 和 matches 为 True。
• 使用 while 循环比较排序后的 alist1 和 alist2 中对应位置的元素是否相等，若相等则将 pos 加 1，不相等则将 matches 设为 False。

解释：

• 此方法先将两个字符串转换为列表，然后对列表排序，由于变位词排序后的字符列表应该完全相同，所以可以通过比较排序后的列表元素是否完全一致来判断是否为变位词。

可以使用 == 来简化代码

def anagram_solution2(s1, s2):
    if len(s1) != len(s2):  # 先比较长度，如果长度不同直接返回 False
        return False
    alist1 = list(s1)
    alist2 = list(s2)
    alist1.sort()
    alist2.sort()
    if alist1 == alist2:
    	return True
    else:
    	return False

时间复杂度：

• 整体的时间复杂度主要由排序操作决定，因此该函数的时间复杂度为

  O(nlogn)

简化函数代码解释：

• 这个函数首先会检查输入的两个字符串的长度是否相同，如果不同，函数会直接返回 False，因为它们不可能是变位词。
• 然后将两个字符串转换为列表，这样可以方便地对字符进行排序操作。
• 对两个列表进行排序，排序后如果两个列表完全相同，那么输入的两个字符串就是变位词，函数返回 True；否则返回 False。

这个函数利用了排序的性质，因为变位词排序后的字符顺序应该是相同的，所以排序后的列表也应该相同。

需要注意的是，由于使用了排序操作，该函数的性能在处理较长字符串时会受到一定影响，不过 Python 的内置排序算法相对高效，对于大多数情况应该可以满足需求。