leetcode49 字母异位词分组

发布于:2025-07-03 ⋅ 阅读:(19) ⋅ 点赞:(0)

题目

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释:

  • 在 strs 中没有字符串可以通过重新排列来形成 "bat"
  • 字符串 "nat" 和 "tan" 是字母异位词,因为它们可以重新排列以形成彼此。
  • 字符串 "ate" ,"eat" 和 "tea" 是字母异位词,因为它们可以重新排列以形成彼此。

题解

本题的关键是怎样寻找异位词并且存储异位词?想到了利用哈希表,python里利用字典实现哈希表,于是问题变成了字典的键怎么设定,题解给了一个很好的答案,用排序后的每个字符串,这样不同的字符串异位词映射的就是同一个算法,思路还是太巧妙了,有在认真的学习哈希表

在实现的过程中,还是遇到了一些意想不到的问题,比如python的排序算法是为列表内置的,那我应该怎样为字符串排序,于是自己实现了一个选择排序(找最小+嵌套有序遍历),这个找最小里需要每次移除最小字符串,但是自己没考虑到重复移除的情况,错了一些题,后面发现replace里有次数移除,python真厉害呀;中间还有一个空字符串无法排序和寻找最小问题,平时写代码要考虑健壮性哇

哈希有数组和map两种实现方式,map参考上一段排序为键,数组利用hash[26]=0为初始值,这个适合范围不大的数组

选择排序+哈希表

class Solution:
    # 对于输入列表,遍历,每个都重新排序,作为新的字符串数组的键值对
    # 每进入一个新的字符串数组,都排序,然后检查是否有已有键值对,如果没有,则新建一个键值对,值添加为这个字符串
    def findsmall(self,str3):
        if str3 == '':
            return str3
        smallstr = str3[0]
        for strx in str3:
            if strx < smallstr:
                smallstr=strx
        return smallstr

    def selectionsort(self, str1):
        # 对输入字符串进行重新排列
        newstr=''
        len1 = len(str1)
        if len1==0:
            return str1
        for i in range(len1):
            x = self.findsmall(str1)
            newstr+=x
            # 仅删除匹配的第一个字符
            str1=str1.replace(x,'',1)
        return newstr

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hash1={}
        for str1 in strs:
            print(str1)
            sorted_str1 = self.selectionsort(str1)
            print(sorted_str1) 
            if sorted_str1 in hash1:
                hash1[sorted_str1].append(str1)
            else:
                hash1[sorted_str1]=[]
                hash1[sorted_str1].append(str1)
        return list(hash1.values())

内置排序+哈希表

class Solution:
    # 对于输入列表,遍历,每个都重新排序,作为新的字符串数组的键值对
    # 每进入一个新的字符串数组,都排序,然后检查是否有已有键值对,如果没有,则新建一个键值对,值添加为这个字符串
    
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hash1={}
        for str1 in strs:
            print(str1)
            sorted_str1 = ''.join(sorted(str1))
            print(sorted_str1) 
            if sorted_str1 in hash1:
                hash1[sorted_str1].append(str1)
            else:
                hash1[sorted_str1]=[]
                hash1[sorted_str1].append(str1)
        return list(hash1.values())

        

哈希数组+内置排序

 def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hash1={}
        for str1 in strs:
            print(str1)
            count=[0]*26
            for i in str1:
                count[ord(i)-ord('a')]+=1
            if tuple(count) in hash1:
                hash1[tuple(count)].append(str1)
            else:
                hash1[tuple(count)]=[]
                hash1[tuple(count)].append(str1)
       
        return list(hash1.values())

参考答案极简版

它相对于数组哈希的改进只有自动初始化一个字典,这个字典的初始值是一个空列表

你的代码已经比较高效了,但可以通过使用 `collections.defaultdict` 来进一步简化逻辑,避免手动检查键是否存在。以下是优化后的代码:

### 优化后的代码
```python
from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            groups[tuple(count)].append(s)
        return list(groups.values())
```

### 优化点说明
1. **使用 `defaultdict`**:
   - `defaultdict(list)` 会自动初始化不存在的键为一个空列表,因此无需手动检查键是否存在。
   - 原代码中的 `if-else` 逻辑可以简化为直接 `append`。

2. **变量名简化**:
   - 将 `hash1` 改为更具描述性的 `groups`。
   - 将 `str1` 改为更简洁的 `s`,`i` 改为 `c`(表示字符)。

3. **移除调试语句**:
   - 删除了 `print(str1)`,因为它在最终代码中不需要。

### 进一步简化(使用排序作为键)
如果你不介意稍微降低一点性能(但代码更简洁),可以使用排序后的字符串作为键:
```python
from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for s in strs:
            groups[''.join(sorted(s))].append(s)
        return list(groups.values())
```

### 两种方法的对比
| 方法               | 时间复杂度       | 空间复杂度 | 适用场景                     |
|--------------------|------------------|------------|------------------------------|
| **字母计数(优化后)** | O(N * L)        | O(N * L)   | 字符串较长或字符范围固定时   |
| **排序作为键**      | O(N * L log L)  | O(N * L)   | 代码简洁,适合短字符串       |

### 总结
- **如果你追求最高性能**,使用字母计数的方法(第一个优化代码)。
- **如果你追求代码简洁**,使用排序作为键的方法(第二个简化代码)。

两种方法都是正确的,选择取决于你的具体需求! 🚀

我的思考

也是借着这个机会重新复习一下排序,感谢whd老师,我学习的算法底子还在,学一学还是可以捡起来。

字符串怎么排序

list内置直接可以排序,sorted()可以对所有可迭代对象排序,list.sort()只能对列表排序

怎样列表化输出字典的所有键

list(hash.values())

怎样可以让字典的键值里添加很多值

先初始化为空列表,然后添加

选择排序怎么定义

遍历,然后每次都找当前最小值。需要内置函数

了解一下python的内置排序

既可以为列表,字符串等不同对象排序,也可以根据key和lambda来排序

Python 提供了多种排序方式,主要包括 **内置排序函数** 和 **列表排序方法**,适用于不同场景。以下是详细总结:

---

### 1. **内置排序函数 `sorted()`**
- **功能**:对任意可迭代对象排序,**返回新列表**,原数据不变。
- **语法**:
  ```python
  sorted(iterable, key=None, reverse=False)
  ```
- **特点**:
  - 支持所有可迭代对象(列表、字符串、元组、字典等)。
  - 通过 `key` 参数自定义排序规则。
  - 稳定排序(相等元素的顺序不变)。

#### 示例:
```python
# 对列表排序
nums = [3, 1, 4, 2]
sorted_nums = sorted(nums)  # 输出: [1, 2, 3, 4]

# 对字符串排序(按字符ASCII值)
s = "hello"
sorted_s = sorted(s)  # 输出: ['e', 'h', 'l', 'l', 'o']

# 按字符串长度排序
words = ["apple", "banana", "cherry"]
sorted_words = sorted(words, key=len)  # 输出: ['apple', 'cherry', 'banana']

# 按字典值排序
data = [{"name": "Alice", "age": 25}, {"name": "Bob", "age": 20}]
sorted_data = sorted(data, key=lambda x: x["age"])
```

---

### 2. **列表方法 `list.sort()`**
- **功能**:原地排序列表,**直接修改原列表**,返回 `None`。
- **语法**:
  ```python
  list.sort(key=None, reverse=False)
  ```
- **特点**:
  - 仅适用于列表。
  - 性能略优于 `sorted()`(因无需创建新列表)。

#### 示例:
```python
nums = [3, 1, 4, 2]
nums.sort()  # nums 变为 [1, 2, 3, 4]
```

---

### 3. **关键参数 `key` 的用法**
通过 `key` 指定排序依据,常见场景:
- **按元素某属性排序**:
  ```python
  students = [("Alice", 90), ("Bob", 85), ("Charlie", 92)]
  students.sort(key=lambda x: x[1])  # 按分数排序
  ```
- **多级排序**:
  ```python
  # 先按分数降序,再按名字升序
  students.sort(key=lambda x: (-x[1], x[0]))
  ```

---

### 4. **降序排序**
设置 `reverse=True`:
```python
nums = [3, 1, 4, 2]
sorted_nums = sorted(nums, reverse=True)  # 输出: [4, 3, 2, 1]
```

---

### 5. **特殊排序场景**
#### (1)对字典排序
- **按键排序**:
  ```python
  d = {"b": 2, "a": 1, "c": 3}
  sorted_keys = sorted(d.keys())  # 输出: ['a', 'b', 'c']
  ```
- **按值排序**:
  ```python
  sorted_items = sorted(d.items(), key=lambda x: x[1])  # 输出: [('a', 1), ('b', 2), ('c', 3)]
  ```

#### (2)自定义对象排序
```python
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

people = [Person("Alice", 25), Person("Bob", 20)]
sorted_people = sorted(people, key=lambda x: x.age)
```

---

### 6. **性能对比**
| 方法          | 时间复杂度 | 空间复杂度 | 是否修改原数据 |
|---------------|------------|------------|----------------|
| `sorted()`    | \(O(n \log n)\) | \(O(n)\)   | 否             |
| `list.sort()` | \(O(n \log n)\) | \(O(1)\)   | 是             |

---

### 7. **注意事项**
1. **字符串排序**:按 Unicode 码点排序(可能不符合语言习惯)。
   ```python
   words = ["苹果", "Banana", "apple"]
   sorted_words = sorted(words)  # 输出: ['Banana', 'apple', '苹果']
   ```
2. **混合类型排序**:Python 3 不允许直接比较不同类型(如 `str` 和 `int`)。

---

### 总结
- 需要新列表 → `sorted(iterable)`
- 原地修改列表 → `list.sort()`
- 复杂排序规则 → 使用 `key` 和 `lambda`

掌握这些方法后,可以高效处理绝大多数排序需求! 🚀

### 按值排序和多级排序详解

#### 1. **按值排序**
当需要对字典的 **值(value)** 进行排序时,可以通过 `sorted()` 的 `key` 参数指定排序依据。

##### 示例代码:
```python
d = {"b": 2, "a": 1, "c": 3}
sorted_items = sorted(d.items(), key=lambda x: x[1])
print(sorted_items)  # 输出: [('a', 1), ('b', 2), ('c', 3)]
```

##### 关键点解析:
- **`d.items()`**:  
  将字典转换为可迭代的 `(key, value)` 元组列表,例如:
  ```python
  [('b', 2), ('a', 1), ('c', 3)]
  ```
- **`key=lambda x: x[1]`**:  
  - `lambda x: x[1]` 是一个匿名函数,表示对每个元组 `x`,取其第二个元素(即 `value`)作为排序依据。
  - 相当于:
    ```python
    def get_value(item):
        return item[1]
    sorted_items = sorted(d.items(), key=get_value)
    ```

#### 2. **多级排序**
当需要按多个条件排序时(例如先按值升序,值相同再按键降序),可以通过 `key` 返回一个元组实现。

##### 示例代码:
```python
d = {"b": 2, "a": 2, "c": 1, "d": 1}
# 按值升序,值相同则按键降序
sorted_items = sorted(d.items(), key=lambda x: (x[1], -ord(x[0])))
print(sorted_items)  # 输出: [('d', 1), ('c', 1), ('b', 2), ('a', 2)]
```

##### 关键点解析:
- **`key=lambda x: (x[1], -ord(x[0]))`**:  
  - 先按 `x[1]`(值)升序排列。
  - 若值相同,则按 `-ord(x[0])`(键的 ASCII 码取负,实现降序)排序。
  - 元组比较规则:从左到右依次比较各元素。

#### 3. **常见场景**
- **按值降序**:
  ```python
  sorted_items = sorted(d.items(), key=lambda x: -x[1])
  ```
- **按键排序**(默认行为):
  ```python
  sorted_items = sorted(d.items())  # 按键升序
  ```
- **混合排序**(如先按值,再按键):
  ```python
  sorted_items = sorted(d.items(), key=lambda x: (x[1], x[0]))
  ```

#### 4. **可视化对比**
| 原始字典          | 排序依据                | 输出结果                     |
|-------------------|-------------------------|------------------------------|
| `{'b':2, 'a':1}`  | `key=lambda x: x[1]`    | `[('a',1), ('b',2)]`         |
| `{'b':2, 'a':2}`  | `key=lambda x: -x[1]`   | `[('b',2), ('a',2)]`         |
| `{'b':2, 'a':2}`  | `key=lambda x: (x[1], -ord(x[0]))` | `[('b',2), ('a',2)]` |

#### 5. **注意事项**
- **字典无序性**:Python 3.7+ 中字典保持插入顺序,但排序时应显式使用 `items()`。
- **复杂键函数**:若排序逻辑复杂,可定义普通函数替代 `lambda`。

通过灵活组合 `key` 和元组,可以实现任意多级排序需求!