题解 | #字符串的排列#

这道题的解法和 #有重复项的数组全排列# 一模一样。。。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    vector<string> Permutation(string str) {
      if (str.empty()) {
        return std::vector<std::string>();
      }
      std::string tmp;
      std::vector<std::string> res;
      std::vector<int> visited(str.size(), 0);
      
      std::sort(str.begin(), str.end());
      
      recursion(res, str, tmp, visited);
      
      return res;
    }
  private:
    void recursion(std::vector<std::string> &res, std::string &str, std::string &tmp, std::vector<int> &visited) {
      if (tmp.size() == str.size()) {
        res.push_back(tmp);
        return ;
      }
      
      for (int i = 0; i < str.size(); ++i) {
        if (visited[i]) {
          continue;
        }
        //  这一步判断的前提是，序列已经是有序的
        if (i > 0 && str[i] == str[i - 1] && !visited[i - 1]) {
          continue;
        }
        
        visited[i] = 1;
        tmp.push_back(str[i]);
        recursion(res, str, tmp, visited);
        tmp.pop_back();
        visited[i] = 0;
      }
    }
};