前端算法:JavaScript实现字符串全排列

我个人认为前端工程师笔试题中,算法题一般不难,也就这个难度,甚至比这还要简单。这是我在笔试过程中遇到的一个题~下面分享一下解题思路。

大体结构:定义一个方法,传入str变量,返回一个数组,包含所有排列:

function fun(str){ 
   var result = []; 
   return result;
}

主要逻辑:肯定是需要递归的~先将第一个字母取出,然后将剩下的字符串全排列。将这个字母,依次插入到每个排列所有缝隙。 如:abc进行全排列,取出a,得到全排列bc和cb,先向bc插,可以得到abc,bac,bca;再向cb插,得到acb,cab,cba;

if(str.length == 1 || str.length == 0 ){
   result.push(str);
   return result;
}else{
   var one = str.substr(0,1);
   var left = str.substr(1);
   var leftResult = fun(left);
   for(i=0;i<leftResult.length;i++){
      for(j=0;j<leftResult[i].length+1;j++){//加1的目的是让字符one也可以插入到最后一个位置
         result.push(leftResult[i].slice(0,j) + one + leftResult[i].slice(j));
      }
   }
}

这样就能实现字符串的全排列啦~

思路有了,可以用数组的迭代方法来实现:

const anagrams = str => {
   if (str.length <= 2) return str.length === 2 ? [str, str[1] + str[0]] : [str];
   return str.split('').reduce((acc, letter, i) =>acc.concat(anagrams(str.slice(0, i) + str.slice(i + 1)).map(val => letter + val)), [])
};

文章链接:http://www.xszzz.com/2019/05/1503.html  本站文章除注明外皆为原创,若侵犯您权益请留言告知,我们会及时处理。

关于本站站长:洃少

醉风云博主,爱好建站和视觉设计。曾从事物资管理、产品运营,现为Web全栈工程师。