题解 | #字符串的排列#
字符串的排列
http://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7
直接上代码
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 };
模拟一下过程,便于理解
e.g. str = 'abc'
第一趟
- res:[''] temp:[] char:'a' cur:''
j:0
cur.slice(0,j)+char+cur.slice(j):'a'
add操作之后,temp:['a']
更新res:['a']
第二趟
- res:['a'] temp:[] char:'b' cur:'a'
j:1
cur.slice(0,j)+char+cur.slice(j):'ab'
add操作之后,temp:['ab']
j:0
cur.slice(0,j)+char+cur.slice(j):'b'
add操作之后,temp:['ab','ba']
更新res:['ab','ba']
第三趟
cur有两个取值
3-1. res:['ab','ba'] temp:[] char:'c' cur:'ab'
j:2
cur.slice(0,j)+char+cur.slice(j):'abc'
add操作之后,temp:['abc']
j:1
cur.slice(0,j)+char+cur.slice(j):'acb'
add操作之后,temp:['abc','acb']
j:0
cur.slice(0,j)+char+cur.slice(j):'cab'
add操作之后,temp:['abc','acb','cab']3-2. res:['ab','ba'] temp:['abc','acb','cab'] char:'c' cur:'ba'
j:2
cur.slice(0,j)+char+cur.slice(j):'bac'
add操作之后,temp:['abc','acb','cab','bac']
j:1
cur.slice(0,j)+char+cur.slice(j):'bca'
add操作之后,temp:['abc','acb','cab','bac','bca']
j:0
cur.slice(0,j)+char+cur.slice(j):'cba'
add操作之后,temp:['abc','acb','cab','bac','bca','cba']
更新res:['abc','acb','cab','bac','bca','cba']