一：实现Trie（前缀树）

image-20251010220922974

1. 字典树

这是一种用边表示数据的图，节点主要包含两部分，一个是子节点指针，另一部分是用数组模拟的字符数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Trie {
public:
    vector<Trie*> sub;
    bool endFlag;
    Trie() :sub(26), endFlag(false) {}
    
    void insert(string word) {
        Trie* root = this;
        for (auto& ch : word) 
        {
            if (root->sub[ch - 'a'] == nullptr)        // 不存在子节点，创建新的
                root->sub[ch - 'a'] = new Trie();
            root = root->sub[ch - 'a'];       // 移动到子节点
        }
        root->endFlag = true;       // 单词结尾标识
    }
    
    bool search(string word) {
        Trie* root = this;
        for (auto& ch : word) 
        {
            if (root->sub[ch - 'a'] == nullptr) return false;
            root = root->sub[ch - 'a'];
        }
        return root->endFlag;
    }
    
    bool startsWith(string prefix) {
        Trie* root = this;
        for (auto& ch : prefix) 
        {
            if (root->sub[ch - 'a'] == nullptr) return false;
            root = root->sub[ch - 'a'];
        }
        return true;
    }
};

image-20251010220947420

二：全排列

image-20251010230856960

1. 回溯

其本质很像递归和深度优先搜索，类似于走迷宫，先选择一条路，直到达到目标或者发现无法走通进行回退，主要分为三部分：选择、探索、恢复选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> result;
    vector<vector<int>> permute(vector<int>& nums) {
        recursion(nums, 0, nums.size());
        return result;
    }
    void recursion(vector<int>& nums, int left, int right)
    {
        if (left == right)
        {
            result.emplace_back(nums);
            return;
        }
        for (int i = left; i < right; ++i)
        {
            swap(nums[i], nums[left]);
            recursion(nums, left + 1, right);
            swap(nums[left], nums[i]);
        }
    }
};

image-20251010230936446

三：子集

image-20251011100412366

1. 二进制迭代

假如数组包含n个元素，子集的所有可能为2n2^n，因此可以使用一个数值来表示该二进制，然后求出对应的子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> ans;

    vector<vector<int>> subsets(vector<int>& nums) {
        int len = nums.size();
        for (int i = 0; i < (1 << len); ++i)			// 2^n
        {
            vector<int> temp;
            for (int j = 0; j < len; ++j)
            {
                if (i & (1 << j)) temp.emplace_back(nums[j]);			// 判断第j位的值
            }
            ans.emplace_back(temp);
        }
        return ans;
    }
};

image-20251011100507327

2. 递归枚举

逐字符处理，需要考虑每个字符的两种状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    vector<vector<int>> subsets(vector<int>& nums) {
        recursion(0, nums);
        return ans;
    }
    void recursion(int cur, vector<int>& nums)
    {
        if (cur == nums.size())
        {
            ans.emplace_back(temp);
            return;
        }
        temp.emplace_back(nums[cur]);       // 添加字符，存在的情况
        recursion(cur + 1, nums);       // 下一个
        temp.pop_back();            // 该字符不存在的情况
        recursion(cur + 1, nums);
    }
};

image-20251011100518618