一文学会字符串全排列

求解字符串全排列一直是字符串相关问题中最常见的问题之一。虽然看起来很简单，仍困扰着许许多多的Java初学者。本文我们就来给出字符串全排列的解答方案供大家参考。

我们在第一次遇见字符串全排列这个问题的时候不要慌张，放轻松，然后冷静思考，接下来我们来看下如何实现这道题。

首先我们来看下问题是什么。

给定一个字符串，求出这个字符串所有可能出现的排列组合。

如： abc

输出:

[ 'cba', 'bca', 'cab', 'acb', 'bac', 'abc' ]

准备好了吗? 来一起看下如何实现吧。

解答思路：

首先我们来做个假设：

当前给的字符串为 'a' 。那么返回的只有一个排列 [ 'a' ]。

当前给的字符串为 'ab' 。则返回 [ 'ab', 'ba' ]。

当前给的字符串为 'abc' 。则返回 [ 'cba', 'bca', 'cab', 'acb', 'bac', 'abc' ]。

………………

1. 一个字符的情况

乍一看好像没什么规律，不急，我们先来实现以下只有一个字符的情况：

const str = 'a'

function fullPer (str) {

return [str]

}

fullPer(str) // [ 'a' ]

相信这个代码大家都会写。接下来，难度继续深入。

2. 两个字符的情况

第二步，我们需要添加两个字符的情况。两个的情况下，为了便于我们理解，我们使用递归的方式实现。

使用递归我们需要先找到以下几个条件

何时结束：str 的长度为 1 的时候

如何递进：每次留一个字符，然后与剩下的字符相加

返回结果：返回一个数组

const str = 'ab'

function fullPer(str) {

if (str.length <= 1) {

return [str]

}

let result = [] // 定义一个结果集，用来收集所有的排列

for(let i = 0,len = str.length;i < len; i ++) {

let child = str[i] // 保留当前字符

let last = str.replace(child, '') // 获得剩下的所有字符

result.push(fullPer(last)[0] + child) // 将得到的下一个字符与当前字符做拼接

}

return result // 将得到的结果返回

}

fullPer(str) // [ 'ba', 'ab' ]

解释一下：

两个字符的情况下，我们写的代码数量明显比一个字符的情况多很懂，所以不好理解，那我们就来解释一下代码。

代码中，如果我们当前保留的字符是 a 的话，那么下一次传入的就是 b 。然后字符长度为1，不做处理，直接返回一个数组。之后我们将得到的字符b与保留字符a相加，得到 ba

同样的道理，保留字符为 b ，下次传入 a，得到 ab

将两次的结果分别添加到结果集中，返回得到 [ 'ba', 'ab' ]

3. 三个字符的情况

三个字符与两个字符相差不大，只不过我们需要变动得到字符之后的处理。我们来看下代码：

const str = 'abc'

function fullPer(str) {

if (str.length <= 1) {

return [str]

}

let result = []

for(let i = 0,len = str.length;i < len; i ++) {

let child = str[i]

let last = str.replace(child, '')

// 唯一与第二步不一样的地方

const middle = fullPer(last).map(item => item + child)

// 因为这里得到的是一个数组，所以我们需要将result与middle做拼接

result = result.concat(middle)

}

return result

}

fullPer(str) // [ 'cba', 'bca', 'cab', 'acb', 'bac', 'abc' ]

解释一下：

三个字符的情况，我们得到的是一个多元素的数组，所以只能通过遍历的方式都添加上之前所保留的字符child

结果集也不能使用push，得使用 concat 将两个数组做拼接。

4. 三个字符以上的情况

我们先验证一下其他数量字符的情况下，上边的函数能不能用，这里我们就输出结果的总数，不输出具体值了。

// 四个字符

const str = 'abcd'

fullPer(str).length // 24

// 五个字符

const str = 'abcd3'

fullPer(str).length // 120

根据阶乘公式可知，我们得到的是正确答案。我们直到解决完整个问题才发现其实问题本身并不复杂，而是我们容易想的复杂，反而影响了思路。相信看完了本文的小伙伴都能独自完成字符串全排列的解答，也可以在本站的Java零基础入门教程中学习新的解答方法，多给自己一点学习和进步的空间!