字符串的排列_

推荐

Java

偏北

 /**
     * 1、递归算法
     *
     * 解析：http://www.cnblogs.com/cxjchen/p/3932949.html  (感谢该文作者！)
     *
     * 对于无重复值的情况
     *
     * 固定第一个字符，递归取得首位后面的各种字符串组合；
     * 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； *递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
     *
     * 假如有重复值呢？
     * *由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。
     * 例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。
     * 但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。
     * 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。
     *
     * 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，
     * 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！
     *
     *
     * @param str
     * @return
     */

public ArrayList<String> Permutation(String str){

        ArrayList<String> list = new ArrayList<String>();
        if(str!=null && str.length()>0){
            PermutationHelper(str.toCharArray(),0,list);
            Collections.sort(list);
        }
        return list;
    }
    private void PermutationHelper(char[] chars,int i,ArrayList<String> list){
        if(i == chars.length-1){
            list.add(String.valueOf(chars));
        }else{
            Set<Character> charSet = new HashSet<Character>();
            for(int j=i;j<chars.length;++j){
                if(j==i || !charSet.contains(chars[j])){
                    charSet.add(chars[j]);
                    swap(chars,i,j);
                    PermutationHelper(chars,i+1,list);
                    swap(chars,j,i);
                }
            }
        }
    }

    private void swap(char[] cs,int i,int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }

/**
     * 2、字典序排列算法
     *
     * 可参考解析： http://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html  （感谢作者）
     *
     * 一个全排列可看做一个字符串，字符串可有前缀、后缀。
     * 生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。
     * 这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
     *
     * [例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的987654321，
     * 从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。
     *
     * 【例】 如何得到346987521的下一个
     * 1，从尾部往前找第一个P(i-1) < P(i)的位置
     * 3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
     * 最终找到6是第一个变小的数字，记录下6的位置i-1
     *
     * 2，从i位置往后找到最后一个大于6的数
     * 3 4 6 -> 9 -> 8 -> 7 5 2 1
     * 最终找到7的位置，记录位置为m
     *
     * 3，交换位置i-1和m的值
     * 3 4 7 9 8 6 5 2 1
     * 4，倒序i位置后的所有数据
     * 3 4 7 1 2 5 6 8 9
     * 则347125689为346987521的下一个排列
     *
     * @param str
     * @return
     */

public ArrayList<String> Permutation2(String str){
        ArrayList<String> list = new ArrayList<String>();
        if(str==null || str.length()==0){
            return list;
        }
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        list.add(String.valueOf(chars));
        int len = chars.length;
        while(true){
            int lIndex = len-1;
            int rIndex;
            while(lIndex>=1 && chars[lIndex-1]>=chars[lIndex]){
                lIndex--;
            }
            if(lIndex == 0)
                break;
            rIndex = lIndex;
            while(rIndex<len && chars[rIndex]>chars[lIndex-1]){
                rIndex++;
            }
            swap(chars,lIndex-1,rIndex-1);
            reverse(chars,lIndex);

            list.add(String.valueOf(chars));
        }

        return list;
    }

    private void reverse(char[] chars,int k){
        if(chars==null || chars.length<=k)
            return;
        int len = chars.length;
        for(int i=0;i<(len-k)/2;i++){
            int m = k+i;
            int n = len-1-i;
            if(m<=n){
                swap(chars,m,n);
            }
        }

    }

编辑于 2018-12-26 14:11:30 回复(38)

Javascript

哲学家L

我不明白，我这咋就内存超限了

function Permutation(str)
{
    // write code here
    str=str.split('').sort().join('')
    let res=[]
    let cur=''
    let visited={}
    function dfs(n){
        if(n==str.length) {
            res.push(cur)
            return 
        }
        for(let i=0;i<str.length;i++){
            if(i>0&&str[i]==str[i-1]&&!visited[i-1]) continue
            if(!visited[i]){
                 visited[i]=true
                 cur+=str[i]
                 dfs(n+1)
                 cur=cur.slice(0,cur.length-1)
                 visited[i]=false
            }  
        }
    }
    dfs(0)
    return res
}
module.exports = {
    Permutation : Permutation
};

发表于 2022-08-04 11:06:43 回复(1)

Javascript

upye666

发表于 2022-05-24 15:56:46 回复(0)

Javascript

nicole27

function Permutation(str) {
 var result = [];
 if (str.length > 1) {
   //遍历每一项
   for (var m = 0; m < str.length; m++) {
     //拿到当前的元素
     var left = str[m];
     //除当前元素的其他元素组合
     var rest = str.slice(0, m) + str.slice(m + 1, str.length);
     //上一次递归返回的全排列
     var preResult = Permutation(rest);
     //组合在一起
     for (var i = 0; i < preResult.length; i++) {
       var tmp = left + preResult[i]
       result.push(tmp);
     }
   }
 } else if (str.length == 1) {
    result.push(str);
 }
 return [...new Set(result)];
}

发表于 2022-03-30 17:42:56 回复(0)

Javascript

已注销

简单的回溯

function Permutation(str)
{
    // write code here
    let res = []
    const dfs = (path,sameIndex) => {
        if(path.length == str.length) {
            res.push(path)
            return
        }
        
        let control = ""
        for(let i = 0;i < str.length;i++) {
            if(control.includes(str[i]) || sameIndex.includes(i)) continue
            control += str[i]
            dfs(path+str[i],sameIndex.concat(i))
        }
    }
    dfs("",[])
    return res
}
module.exports = {
    Permutation : Permutation
};

发表于 2022-03-22 17:48:30 回复(0)

Javascript

Danae2

发表于 2022-03-02 16:20:07 回复(0)

Javascript

Active_Waylon

function Permutation(str)
{
    // write code here
    //新建结果数组，初始化为空字符串
    let res = [''];
    //遍历给定字符串中的每一个字符
    for (const char of str) {
        //新建一个Set(可以起到剪枝、去重的作用)
        const temp = new Set();
        //对于res数组中的每个字符串
        for(const cur of res){
            //从尾到头依次操作
            for(let j = cur.length; j >=0; j--) {
                //插空
                temp.add(cur.slice(0,j)+char+cur.slice(j));
            }
        }
        //更新res
        res = [...temp];
    }
    // 返回处理完最后得到的res
    return res;
}
module.exports = {
    Permutation : Permutation
};

详情看题解：https://blog.nowcoder.net/n/5a8f9397dea54e5eb50a1aeb9c6e9311

发表于 2021-09-20 21:49:55 回复(0)

Javascript

王志鹏w

用的官方的方法，递归+回溯好理解

这个算法是让每个字符都可以作为一次开头，后面的同理，固定了第一个位置后，剩余的串，也是每一字符都可以作为一次开头，实现了全排列

用js修改下官方的代码，js的字符串不可改变，所以交换位置时，先转成数组交换，再返回字符串，增加了开销

    function Permutation(str) {
      // write code here
      if (str.length == null) return null
      let set = new Set()

      perm(0, str, set)
      return [...set]

      function perm(pos, str, set) {
        if (pos + 1 == str.length) {
          set.add(str)
          return
        }
          
        for (let i = pos; i < str.length; i++) {
          str = swap(pos, i, str)
          perm(pos + 1, str, set)
          str = swap(pos, i, str)
        }
      }
      function swap(a, b, str) {
        let arr = str.split('')
        let temp = arr[a]
        arr[a] = arr[b]
        arr[b] = temp
        return arr.join('')
      }
    }

发表于 2021-09-06 18:51:46 回复(0)

Javascript

牛客477650639号

let result = new Set();

function Permutation(str)
{
    // write code here
    let arr = [...str];
    console.log(arr);
    
    insert('', arr);
    return [...result];
}

function insert(str, arr) {
    if(arr.length == 1) {
        let item = str + arr[0];
        console.log(typeof item)
        console.log(str, arr)
        result.add(item);
    } else {
        for(let i = 0; i < arr.length; i++) {
            let str2 = str + arr[i];
            let arr2 = [...arr];
            arr2.splice(i, 1);
            console.log(str2, arr2);
            insert(str2, arr2);
        }
    }
}

module.exports = {
    Permutation : Permutation
};

发表于 2021-08-31 22:05:26 回复(0)

Javascript

best1201910221528501

发表于 2021-08-10 11:53:06 回复(0)

Javascript

初见呀

不喜欢用递归，大爱回溯，想找个JS的题解都费劲，哎

大家可以去看看利口上面全排列2 那个代码随想录的解法，他讲的很好，这也是我看懂了学过来的

function Permutation(str)
{
        let  res=[]  //类似与全排列，存在重复数字的全排列
        let  path=[]
        let  arr=str.split("")
        arr.sort((a,b)=>a-b)
        let  back=used=>{
            if(path.length==arr.length){
                res.push(path.join(""))
                return 
            }
            for(let i=0;i<arr.length;i++){
                if(i>0 &&arr[i]==arr[i-1]&&!used[i-1]) continue
                if(!used[i]){
                    used[i]=true
                    path.push(arr[i])
                    back(used)
                    path.pop()
                    used[i]=false
                }
            }
        }
        back([])
    return  res
        
    
    // write code here
}

发表于 2021-07-30 21:57:13 回复(0)

Javascript

鑫宝Code

发表于 2021-07-29 11:15:06 回复(0)

JavaScript

Monster-hash

function Permutation(str)
{
    // write code here
    //保存每一轮递归的排列结果
    var result = [];
    //初始条件：长度为1
    if (str.length == 1) {
        return [str]
    } else {
        //求剩余子串的全排列,对每个排列进行遍历
        var preResult = Permutation(str.slice(1));
        for (let j = 0; j < preResult.length; j++) {
            for (let k = 0; k < preResult[j].length + 1; k++) {
                //将首字母插入k位置  
                let temp = preResult[j].slice(0, k) + str[0] + preResult[j].slice(k);
                result.push(temp);
            }
        }
        //return result.sort()//返回排序不去重
        return Array.from(new Set(result.sort())) //返回排序去重结果

    }

}
module.exports = {
    Permutation : Permutation
};

function Permutation(str)
{
    // write code here
    //保存每一轮递归的排列结果
    var result = [];
    //初始条件：长度为1
    if (str.length == 1) {
        return [str]
    } else {
        //求剩余子串的全排列,对每个排列进行遍历
        var preResult = Permutation(str.slice(1));
        for (let j = 0; j < preResult.length; j++) {
            for (let k = 0; k < preResult[j].length + 1; k++) {
                //将首字母插入k位置  
                let temp = preResult[j].slice(0, k) + str[0] + preResult[j].slice(k);
                result.push(temp);
            }
        }
        //return result.sort()//返回排序不去重
        return Array.from(new Set(result.sort())) //返回排序去重结果

    }

}
module.exports = {
    Permutation : Permutation
};

发表于 2021-03-02 02:20:59 回复(0)

JavaScript

别卷啦！

function Permutation(str)
{
    // write code here
    let res = []
    let len = str.length
    const flag = new Array(len).fill(false)
    str = str.split('').sort()
    backPack('')
    return res
    function backPack(s){
        if(s.length == len){
            res.push(s.slice())
            return 
        }
        for(let i = 0;i<str.length;i++){
            if(flag[i] || (i>0&&str[i] == str[i-1] &&!flag[i-1])){
                continue 
            }
            s += str[i]
            flag[i] = true
            backPack(s)
            flag[i] = false
            s = s.substring(0,s.length-1)
        }
    }
}

发表于 2021-01-26 16:33:02 回复(0)

JavaScript

chika23

function Permutation(str) {
    if (str.length == 1) return str;
    let sx = [...str];
    let stra = [];
    for (let i = 0; i < sx.length; i++) {
        let sn = sx[i];
        sx.splice(i, 1);
        Permutation(sx).forEach(s => {
            if (stra.indexOf(sn + s) == -1)
                stra.push(sn + s);
        });
        sx = [...str];
    }
    return stra;
}

编辑于 2020-03-23 15:46:17 回复(0)

JavaScript

atezi

function Permutation(str)
{
    // write code here
    if(str.length==0){return false;}
    var result=[];
    if(str.length==1){
        return [str];
    }else{
        for(var i=0;i<str.length;i++){
            var c=str[i];//遍历str 拿到字符放首位 在与后面全排列拼接
            var newstr=str.slice(0,i)+str.slice(i+1,str.length);
            var r=Permutation(newstr);//递归剩余字符 返回数组
            for(var j=0;j<r.length;j++){
                var temp=c+r[j];//与全排列字符拼接
                result.push(temp);
            }
        }
    }
    return [...new Set(result)];//去重相同叠字符如'aaa'
}

js版本 递归版本思路会清晰点

发表于 2020-03-22 20:39:18 回复(0)

JavaScript

Helianthuswhite

/**
 * 我的解题思路：
 * 没有生命套路与技巧，完全是生解。。。。
 * 1.将字符串分解为字符数组，如果字符串不为空，则初始化结果集为数组的最后一个元素，否则初始化为空
 * 2.当字符数组不为空时，进行遍历
 * 3.获取字符数组的最后一个元素char，并移除原数组中该元素
 * 4.遍历结果集，将char与结果集中的每一个元素进行组合，对于长度为n的元素，共有n + 1种组合方式
 * 5.每次遍历完结果集后，将结果集修改为遍历后的结果，并用该结果进行再次遍历，直到字符数组为空
 * 6.对结果集进行字符排序并返回结果集
 *
 * @param {*} str 
 */
function Permutation(str)
{
    // write code here
    const array = str.split('');
    let result = array.length ? [array.pop()] : [];
    while (array.length) {
        const inner = [];
        const char = array.pop();
        result.forEach(item => {
            const temp = item.split('');
            for (let i = 0; i <= temp.length; i++) {
                temp.splice(i, 0, char);
                inner.indexOf(temp.join('')) === -1 && inner.push(temp.join(''));
                temp.splice(i, 1);
            }
        });
        result = inner;
    }
    return result.sort();
}

/**
 * 评论区TOP的解题思路：
 * 评论区热门的解题思路主要包括递归法及字典序排列法，这里给出字典序排列的解法
 * 1.将字符串分解为字符数组，如果字符串不为空，则初始化结果集为数组的最后一个元素，否则初始化为空
 * 2.从字符串数组的最右边开始，查找到第一个升序序列的位置i
 * 3.从位置i开始向右查找，查找到最后一个比第i位大的元素位j
 * 4.交换第i位和第j位的元素
 * 5.将第i + 1位之后的元素进行逆序
 * 6.将新的字符数组组成的字符串加入到结果集中并对新的字符数组进行遍历，重复2、3、4、5步直到i为0
 *
 * @param {*} str 
 */
function topPermutation(str)
{
    // write code here
    let array = str.split('');
    const result = str ? [array.sort().join('')] : [];
    let i = array.length - 1;
    while (i > 0) {
        i = array.length - 1;
        while (i > 0 && array[i - 1] >= array[i]) {
            i--;
        }
        let j = i;
        while (j < array.length && array[j] > array[i - 1]) {
            j++;
        }
        const temp = array[i - 1];
        array[i - 1] = array[j - 1];
        array[j - 1] = temp;
        const left = array.slice(0, i);
        const right = array.slice(i);
        array = left.concat(right.reverse());
        if (result.indexOf(array.join('')) === -1) {
            result.push(array.join(''));
        }
    }
    return result;
}

发表于 2020-03-09 21:25:40 回复(0)

JavaScript

根号1024

function Permutation(str) {
        var result = []
        if (str===''){ return result }
        var arr = str.split('')
        PermutationStr(arr, result, 0)
        var newResult = []
        for (i in result) {
            if (newResult.indexOf(result[i] === -1)) {
                newResult.push(result[i])
            }
        }
        // 排序
        return newResult.sort()
    }

    // 回溯的思想, 深度遍历, tag用来记录当前移动到下一位要交换的字符的下标
    function PermutationStr(array, result, tag) {
        // 当移动到最后一位时, 存储
        if(tag == array.length) {
            var temp = array.join('')
            // 判断有无重复
            if (result.indexOf(temp) == -1)
                result.push(temp)
        }
        for(var i=tag; i<array.length; i++) {
            // 判断有无重复相邻字符
            if (array[i]!==array[i+1]){
                // 包括自己和自己的交换
                swap(array, i, tag)
                PermutationStr(array, result, tag+1)
                // 交换回来??
                swap(array, i, tag)    
            }
        }
    }

    // 交换位置
    function swap(array, i, j) {
        var temp = array[i]
        array[i] = array[j]
        array[j] = temp
    }

发表于 2019-08-03 10:35:17 回复(0)

JavaScript

Niuke_Li

function Permutation(str)
{
    if(str.length==0) return []
    var array = [str[0]]
    for(let j = 1;j<str.length;j++){
        array = f(array,str[j])
    }
    return [...new Set(array)].sort()
    /* 
     * 下面的 f 函数是向字符串数组 a 中插入一个新字符,返回新的全排列数组, 
     * 例如向['aa']插入'b'得到['baa','aba','aab'] 
    */
    function f(a,ch){
        var o = []
        for(let i=0;i<=a[0].length;i++){
            o = o.concat(a.map(x=>x.slice(0,i)+ch+x.slice(i)))
        }
        return [...new Set(o)]
    }
}

发表于 2019-02-12 00:34:00 回复(0)

字符串的排列

输入描述:

输入

输出

说明

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题