手寫字元串的全排列

• 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;  }