题解 | #字符串的排列#

需要注意

1. 函数的传参，很多都需要&mut
2. String类型转Vec<char> let mut vec_chars: Vec<char> = str.chars().collect();
3. Vec<char>转String let ret_str: String = vec_chars.iter().collect();
4. 使用hashset来去重
5. vec的swap方法用于回溯 vec_chars.swap(start, index);

此外感觉rust在递归上好慢，且占用空间

use std::collections::HashSet;

struct Solution;

impl Solution {
    /// 创建 Solution 的新实例
    fn new() -> Self {
        Solution {}
    }

    /// 生成字符串所有唯一排列
    ///
    /// # 参数
    ///
    /// * `str` - 输入的字符串
    ///
    /// # 返回
    ///
    /// 包含输入字符串所有唯一排列的向量。
    pub fn Permutation(&self, str: String) -> Vec<String> {
        let mut vec_chars: Vec<char> = str.chars().collect();
        let mut ret_set: HashSet<String> = HashSet::new();

        // 生成排列
        self.permutate(&mut vec_chars, 0, &mut ret_set);

        // 将 HashSet 转换为 Vec<String>
        ret_set.into_iter().collect()
    }

    /// 递归辅助函数，用于生成排列
    ///
    /// # 参数
    ///
    /// * `vec_chars` - 字符向量的可变引用
    /// * `start` - 向量中的当前位置
    /// * `ret_set` - 用于存储排列的 HashSet 的可变引用
    fn permutate(&self, vec_chars: &mut Vec<char>, start: usize, ret_set: &mut HashSet<String>) {
        // 如果已经到达字符串的末尾，将向量转换为字符串
        if start == vec_chars.len() - 1 {
            let ret_str: String = vec_chars.iter().collect();
            // 将排列插入 HashSet 以确保唯一性
            ret_set.insert(ret_str);
            return;
        }

        // 通过交换字符递归生成排列
        for index in start..vec_chars.len() {
            vec_chars.swap(start, index);
            self.permutate(vec_chars, start + 1, ret_set);
            vec_chars.swap(start, index);
        }
    }
}