手写字符串的全排列

• 2019 年 10 月 16 日
• 筆記

题目描述如下：

当输入一个字符串时，输出一个字符串的全排列，例如输入，abc,
输出如下：

解决思想时

使用dfs,当保存的目的字符串达到排列字符串最终的长度时，这时需要，把这个字符串保存下来，
然后当前递归结束，递归返回时，在字符串中之前 加入的最后一个字符需要删除掉，然后再返回其他字符串

源程序如下

  #include<iostream>  #include<string>  #include<vector>  #include<cstdlib>  #include<cstring>  #include<set>  using namespace std;      void dfs(set < string > &res, const string & src, string & dst, int *flags,       int dstLen);    vector < string > Permutation(string str)  {      if (str.empty()) {      vector < string > res;      return res;      }      // int flags[10];      int *flags = new int[str.size()];      set < string > strSet;      for (int i = 0; i < str.size(); i++) {      string s;      memset(flags, 0, sizeof(sizeof(int) * str.size()));      s.push_back(str[i]);      flags[i] = 1;      dfs(strSet, str, s, flags, str.size());      }      vector < string > res(strSet.begin(), strSet.end());      delete[]flags;      return res;  }        void dfs(set < string > &res, const string & src, string & dst, int *flags,       int dstLen)  {      if (dst.size() == dstLen) {      res.insert(dst);      return;      }        for (int i = 0; i < src.size(); i++) {      if (!flags[i]) {          flags[i] = 1;          dst.push_back(src[i]);          dfs(res, src, dst, flags, dstLen);          dst.pop_back();          flags[i] = 0;      }        }  }    void testPermutation()  {        string s("abc");      vector < string > res;      res = Permutation(s);      for (int i = 0; i < res.size(); i++) {      cout << res[i] << " " << endl;      }  }        int main()  {      testPermutation();      return 0;  }