题解 | #字符串的排列#

字符串的排列

https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7

1 场景1 某平台闭卷遇到

某平台闭卷遇到

当时难点，没有想清楚 dfs的关系；

没有想清楚，数字、字符串配合的方法；

只在想用数字来组合生成，n=7组合情况还是挺多的；

2参考

右上角下载编辑器中的代码，请注意哈；

java 答案

基础:Arrays.sort, Arrays.fill等加强使用哈；

import java.util.*;
public class Solution {
    public void recursion(ArrayList res, char[] str, StringBuffer temp, boolean[] vis){
        //临时字符串满了加入输出 fast-template
        if(temp.length() == str.length){
            res.add(new String(temp));
            return;
        }
        //遍历所有元素选取一个加入
        for(int i = 0; i < str.length; i++){
            //如果该元素已经被加入了则不需要再加入了
            if(vis[i])
                continue;
            if(i > 0 && str[i - 1] == str[i] && !vis[i - 1])
                //当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
                continue;
            //标记为使用过
            vis[i] = true;
            //加入临时字符串
            temp.append(str[i]);
            recursion(res, str, temp, vis);
            //回溯
            vis[i] = false;
            temp.deleteCharAt(temp.length() - 1);
        }
    }
    public ArrayList Permutation(String str) {
        ArrayList res = new ArrayList();
        if(str == null || str.length() == 0)
            return res;
        //转字符数组
        char[] charStr = str.toCharArray();
        //先按字典序排序，使重复字符串相邻
        Arrays.sort(charStr);
        boolean[] vis = new boolean[str.length()];
        //标记每个位置的字符是否被使用过
        Arrays.fill(vis, false);
        StringBuffer temp = new StringBuffer();
        // 递归获取
        recursion(res, charStr, temp, vis);
        return res;}
}

c++ 答案基于dfs和占位数组

对于重复的处理请注意哈；

String 真的可以push_back,pop_back最后一个元素拉；参考

class Solution {
public:
 void recursion(vector &res, string &str, string &temp, vector &vis){
 //临时字符串满了加入输出 fast-template
 if(temp.length() == str.length()){
 res.push_back(temp);
 return;
 }
 //遍历所有元素选取一个加入
 for(int i = 0; i < str.length(); i++){
 //如果该元素已经被加入了则不需要再加入了
 if(vis[i])
 continue;
    //-----很棒的地方哈；
 if(i > 0 && str[i - 1] == str[i] && !vis[i - 1])
 //当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
 continue；
 //标记为使用过
 vis[i] = 1;
 //加入临时字符串
 temp.push_back(str[i]);
 recursion(res, str, temp, vis);
 //回溯
 vis[i] = 0;
 temp.pop_back();
 }
 }
 vector Permutation(string str) {
 //先按字典序排序，使重复字符串相邻
 sort(str.begin(), str.end());
 //标记每个位置的字符是否被使用过
 vector vis(str.size(), 0);
 vector res;
 string temp;
 // 递归获取
 recursion(res, str, temp, vis);
 return res;
 }
};

c++答案基于dfs和交换

class Solution {
public:
  void dfs(int h,string s,set &ans){
      if(h==s.size()-1){//递归边界
          ans.insert(s);//找到一个排序，并且插入
          return ;
      }
      for(int i=h;i<s.size();i++){//假设原来的元素映射到他的下标，那么我们搜索的是下标的全排序
          swap(s[i],s[h]);
          dfs(h+1,s,ans);//进入下一层递归
          swap(s[i],s[h]);//还原s
      }
  }
  vector Permutation(string str) {
      if(str.empty())return {};
      set ans;//因为题目说str中可能有重复元素，所以需要集合来去重,并且起到从小到大排序作用
      dfs(0,str,ans);//开始搜索字符串
      return vector({ans.begin(),ans.end()});//vector迭代器拷贝初始化，只需要元素的类型一样即可，跟容器无关
  }
};



class Solution {
public:
    //try to help with set and THink with swap, less code More think
    vector<string> Permutation(string str) {
            std::vector<string> vec2 = {}; // new vector<string> ();
        //if( str == nullptr || str.length() ==0)
        if(str.empty())
            return vec2;


        set<string> okSet = {}; //new set<string>() ;
        dfs(0,str, okSet);


        //add {} ,匿名cplus object
        return vector<string>({ okSet.begin(),okSet.end() }); 
        //new vector<string>({ okSet.begin(),okSet.end() });


    }
    void dfs(int h , string str, set<string> & set){


           //pre ,no need to sort.
            
            if(h==str.length()-1){
                //set.add(str);  //API没对
                set.insert(str);
                return;
            }
           //no need to check vis


           //no need to check same exist


            for(int i = h ; i<= str.length()-1 ; i++){
                
                //string 对象不能 +数字？
                std::swap(str[i] , str[h] );


                //容易出错的地方， 需要理解下面标签
                dfs(h+1,str, set);


                std::swap(str[h] , str[i] );
            }
            


    }


};