Ex38 字符串的排列

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

解题思路

这个题要使用回溯算法，核心点是将两个字符交换来完成所有的排列。先固定一个字符，然后再去递归地完成剩下的字符。

另外，以下的代码使用了一个unordered_set来去重，以应对这样的case"aab"。

代码

class Solution
{
public:
  std::vector<std::string>
  permutation (std::string s)
  {
    std::vector<std::string> rtn;
    if (s.size () == 0)
      return rtn;
    if (s.size () == 1)
      {
        rtn.push_back (s);
        return rtn;
      }
    std::string str (s);
    std::unordered_set<std::string> unique;
    permutation_core (rtn, str, 0, unique);
    return rtn;
  }

private:
  void
  permutation_core (std::vector<std::string> &rtn, std::string str, int index,
                    std::unordered_set<std::string> &unique)
  {
    if (index >= str.size ())
      {
        if (unique.find (str) == unique.end ())
          {
            rtn.push_back (str);
            unique.insert (str);
          }
      }
    else
      {
        for (int i = index; i < str.size (); ++i)
          {
            char tmp = str[index];
            str[index] = str[i];
            str[i] = tmp;
            permutation_core (rtn, str, index + 1, unique);
            tmp = str[i];
            str[i] = str[index];
            str[index] = tmp;
          }
      }
  }
};

结果

执行结果：通过

执行用时：136 ms, 在所有 C++ 提交中击败了53.40%的用户

内存消耗：25 MB, 在所有 C++ 提交中击败了38.63%的用户