[数据结构与算法] 【算法】JZ38 字符串的排列（全排列问题，DFS）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【算法】JZ38 字符串的排列（全排列问题，DFS） -> 正文阅读

[数据结构与算法]【算法】JZ38 字符串的排列（全排列问题，DFS）

题目链接

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

在这里插入图片描述

回溯法

使用回溯法，本质将字符串看成多叉树的形式。

1、添加当前数据
2、剪枝（因为会存在重复的字符串）
3、DFS
4、回退一步

class Solution {
public:
    bool IsExist(vector<string>& ret, string str)
    {
        for(auto i : ret)
        {
            if(i == str)
                return true;
        }
        return false;
    }
    
    void swap(string& str, int start, int end)
    {
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
    }
    
    void _Permutation(string& str, int start, vector<string>& ret)
    {
        // 添加值
        if(start == str.size()-1)
        {
            // 去重剪枝
            if(!IsExist(ret, str))
            {
                ret.push_back(str);
                return;
            }
        }
        
        // DFS
        for(int i = start; i < str.size(); ++i)
        {
            swap(str, start, i);
            _Permutation(str, start+1, ret);
            swap(str, start, i);
        }
    }
    
    vector<string> Permutation(string str) {
        vector<string> result; // 结果集
        if(str.size() == 0)
            return result;
        
        _Permutation(str, 0, result);
        return result;
    }
};