python算法学习之大O表示法与变位词

大O表示法#

大O表示法（Big O Notation）是用于描述算法时间复杂度的数学符号，表示算法的运行时间或空间需求随输入规模增长的变化趋势。例如：实际运行时间：T(n) = 3n² + 2n + 100 大O表示：O(n²) ← 只保留最高阶项，忽略系数当n很大时：n=1000: 3*(1000²)=3,000,000 vs 2*1000=2000 vs 100 低阶项和常数可以忽略不计！

一、什么是变位词？#

变位词（Anagram）是指由相同字母重新排列形成的单词或短语。核心特征

1
字母相同：包含完全相同的字母集合
2

3
顺序不同：字母的排列顺序不同
4

5
长度相同：单词长度必须相等
6

7
大小写无关：通常忽略大小写差异

变位词示例#

1
```python
2
anagram_pairs = [
3
    ("listen", "silent"),      # 经典例子
4
    ("earth", "heart"),        # 字母重组
5
    ("evil", "vile"),          # 短词变位
6
    ("debit card", "bad credit"),  # 短语变位
7
    ("Eleven plus two", "Twelve plus one"),  # 有趣的长短语
8
]
9
```

非变位词示例#

1
```python
2
not_anagrams = [
3
    ("hello", "hell"),         # 长度不同
4
    ("test", "best"),          # 字母不同
5
    ("apple", "apples"),       # 字母数量不同
6
]
7
```

二、判断变位词的多种方法#

1：排序比较法#

1
```python
2
def is_anagram_sort(s1: str, s2: str) -> bool:
3
    """方法1：排序比较 - O(n log n)时间，O(n)空间"""
4
    # 清理字符串：去空格、转小写
5
    s1_clean = ''.join(s1.lower().split())
6
    s2_clean = ''.join(s2.lower().split())
7
    # 长度不同直接返回False
8
    if len(s1_clean) != len(s2_clean):
9
        return False
10
    # 排序后比较
11
    return sorted(s1_clean) == sorted(s2_clean)
12
```

方法2：字符计数法#

1
```python
2
def is_anagram_counter(s1: str, s2: str) -> bool:
3
    """方法2：字符计数 - O(n)时间，O(1)空间（固定大小数组）"""
4
    # 清理字符串
5
    s1_clean = ''.join(s1.lower().split())
6
    s2_clean = ''.join(s2.lower().split())
7

8
    if len(s1_clean) != len(s2_clean):
9
        return False
10

11
    # 假设只包含小写英文字母（26个）
12
    counter = [0] * 26
13

14
    # 统计第一个字符串的字符频率
15
    for ch in s1_clean:
16
        if 'a' <= ch <= 'z':
17
            counter[ord(ch) - ord('a')] += 1
18

19
    # 减去第二个字符串的字符频率
20
    for ch in s2_clean:
21
        if 'a' <= ch <= 'z':
22
            index = ord(ch) - ord('a')
23
            counter[index] -= 1
24
            if counter[index] < 0:  # 提前结束
25
                return False
26

27
    # 检查是否所有计数都为0
28
    return all(count == 0 for count in counter)
29

30
```

方法3：质数乘积法（巧妙但有限制）#

1
```python
2
def is_anagram_prime(s1: str, s2: str) -> bool:
3
    """方法3：质数乘积法 - O(n)时间，O(1)空间"""
4
    # 给每个字母分配一个唯一的质数
5
    primes = {
6
        'a': 2, 'b': 3, 'c': 5, 'd': 7, 'e': 11,
7
        'f': 13, 'g': 17, 'h': 19, 'i': 23, 'j': 29,
8
        'k': 31, 'l': 37, 'm': 41, 'n': 43, 'o': 47,
9
        'p': 53, 'q': 59, 'r': 61, 's': 67, 't': 71,
10
        'u': 73, 'v': 79, 'w': 83, 'x': 89, 'y': 97, 'z': 101
11
    }
12

13
    s1_clean = ''.join(s1.lower().split())
14
    s2_clean = ''.join(s2.lower().split())
15

16
    if len(s1_clean) != len(s2_clean):
17
        return False
18

19
    def calculate_product(s):
20
        product = 1
21
        for ch in s:
22
            if 'a' <= ch <= 'z':
23
                product *= primes[ch]
24
        return product
25

26
    return calculate_product(s1_clean) == calculate_product(s2_clean)
27
```

CodeTailor