变位词问题的解法及其时间复杂度分析

超級の新人

Announcement

私のブログにご訪問いただき、ありがとうございます！

Learn More

标签

469 字

2 分钟

变位词问题的解法及其时间复杂度分析

2026-01-12

算法

检查两个词是否为变位词

比如python和typthon、heart和earth

1
def anagramSolution1(s1,s2):
2
    stillOK = True
3
    alist = list(s2)
4
    pos1 = 0
5
    while pos1 < len(s1) and stillOK:
6
        pos2 = 0
7
        found = False
8
        while pos2 < len(list(s2)) and not found:
9
            if s1[pos1] == alist[pos2]:
10
                found = True
11
            else:
12
                pos2 = pos2 + 1
13
        if found:
14
            alist[pos2] = None
15
        else:
16
            stillOK = False
17
        pos1 = pos1 + 1
18
    return stillOK

逐字检查算法复杂度分析

外层循环遍历s1为n，内层循环为 1~n其中的一个数

所以最终执行次数为1+2+…+n = n(n+1)/2 = n^2

因此O(n^2)

1
def anagramSolution2(s1,s2):
2
    '''
3
    最简
4
    return sort(s1) == sort(s1)
5
    '''
6
    alist1 = list(s1)
7
    alist2 = list(s2)
8

9
    alist1.sort() #sort()的时间复杂度为O(n log n)
10
    alist2.sort()
11
    stillOK = True
12
    pos = 0
13
    while pos < len(s1) and stillOK: # O(n)
14
        if alist1[pos] == alist2[pos]:
15
            pos = pos + 1
16
        else:
17
            stillOK = False
18
    return stillOK

排序比较算法复杂度分析取最大为O(n log n)

1
def anagramSolution3(s1,s2):
2
    '''
3
    以下是伪代码
4
    将s1进行全排列之后将s2与每一种可能性进行比较
5
    若成功则输出True
6
    '''
7
    stillOK = True
8
    return stillOK

暴力法算法复杂度分析

总执行次数为 n*(n-1)*…21 = n!

O(n!)非常大 O(n!) > O(2^n)

1
print(anagramSolution3('python','typhon'))
2

3
def anagramSolution4(s1,s2):
4
    stillOK = True
5
    c1 = [0] * 26
6
    c2 = [0] * 26
7

8
    for i in range(len(s1)):
9
        pos = ord(s1[i]) - ord('a') #ord函数用来返回一个字符的unicode编码
10
        c1[pos] = c1[pos] + 1   #c1[pos]处的值+1
11
    for i in range(len(s2)):
12
        pos = ord(s2[i]) - ord('a') #减去之后正好对应0~25的索引
13
        c2[pos] = c2[pos] + 1
14

15
    j = 0
16
    while j < 26 and stillOK: #遍历每一个计数器
17
        if c1[j] == c2[j]:
18
            j = j + 1
19
        else:
20
            stillOK = False
21
    return stillOK

计数比较算法复杂度分析总执行次数为T(n) = 2n + 26 所以为O(n)

扩展：使用哈希表

1
def anagramSolution4(s1, s2):
2
    count1 = {}
3
    count2 = {}
4

5
    for char in s1:
6
        count1[char] = count1.get(char, 0) + 1
7
    #会储存为{'p': 1, 'y': 1, 't': 1, 'h': 1, 'o': 1, 'n': 1}
8
    for char in s2:
9
        count2[char] = count2.get(char, 0) + 1
10

11
    return count1 == count2
12
    #时间复杂度也为O(n)