括号生成、子集和电话号码的字母组合

括号生成

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
示例
1
例如,给出 n = 3,生成结果为:
2
3
[
4
"((()))",
5
"(()())",
6
"(())()",
7
"()(())",
8
"()()()"
9
]
Copied!

方法一 回溯法(实现一)

思路
我们知道,有且仅有两种情况,生成的括号序列不合法
  • 我们不停的加左括号,其实如果左括号超过 n 的时候,它肯定不是合法序列了。因为合法序列一定是 n 个左括号和 n 个右括号。
  • 如果添加括号的过程中,如果右括号的总数量大于左括号的总数量了,后边不论再添加什么,它都不可能是合法序列了。
基于上边的两点,我们只要避免它们,就可以保证我们生成的括号一定是合法的了。
详解
  1. 1.
    采用回溯法,即把问题的解空间转化成了图或者树的结构表示,然后,使用深度优先搜索策略进行遍历,遍历的过程中记录和寻找所有可行解或者最优解。
  2. 2.
    如果自定义的字符串长度足够且走到这里,那么就说明这个组合是合适的,我们把它保存。
  3. 3.
    否则,递归执行添加左括号,添加右括号的操作。
  4. 4.
    递归结束条件为结果字符串长度等于左右括号的总个数(2n),则返回最终结果。
代码
1
/**
2
* @param {number} n
3
* @return {string[]}
4
*/
5
const generateParenthesis = n => {
6
const res = [];
7
const gen = (str = '', l = 0, r = 0) => {
8
// 如果自定义的字符串长度足够且走到这里,那么就说明这个组合是合适的
9
if (str.length === 2 * n) {
10
res.push(str);
11
return;
12
}
13
// 下面的逻辑:左括号必须出现在右括号的前面
14
// 只有在 l >= n 的 时候,才不能添加左括号,其他都可添加
15
if (l < n) {
16
gen(`${str}(`, l + 1, r);
17
}
18
// 如果右括号没有左括号多,我们就可以添加一个右括号
19
if (r < l) {
20
gen(`${str})`, l, r + 1);
21
}
22
};
23
gen();
24
return res;
25
};
Copied!
复杂度分析
我们的复杂度分析依赖于理解 generateParenthesis(n) 中有多少个元素。这个分析需要更多的背景来解释,但事实证明这是第 n 个卡塔兰数
1n+1(2nn)\dfrac{1}{n+1}\binom{2n}{n}
,这是由
4nnn\dfrac{4^n}{n\sqrt{n}}
渐近界定的。
  • 时间复杂度:
    O(4nn)O(\dfrac{4^n}{\sqrt{n}})
    ,在回溯过程中,每个有效序列最多需要 n 步。
  • 空间复杂度:
    O(4nn)O(\dfrac{4^n}{\sqrt{n}})
    ,如上所述,并使用
    O(n)O(n)
    的空间来存储序列。

方法二 回溯法(实现二)

思路
整体的实现思路也是回溯法,也是递归来实现该思路,唯一不同的是,递归的结束条件是左右括号都消费尽。
详解
  1. 1.
    采用回溯法,即把问题的解空间转化成了图或者树的结构表示,然后,使用深度优先搜索策略进行遍历,遍历的过程中记录和寻找所有可行解或者最优解。
  2. 2.
    首先,先从左括号开始填充。
  3. 3.
    然后,填充右括号,保证两类括号数目一致,平衡。
  4. 4.
    递归结束条件为左右括号均消费尽,则输出结果。
代码
1
/**
2
* @param {number} n
3
* @return {number}
4
*/
5
const generateParenthesis = n => {
6
const res = [];
7
// left :左括号个数, right:右括号个数
8
function helper (left, right, max, str) {
9
if (left === max && right === max) {
10
res.push(str);
11
return;
12
}
13
// 先从左括号开始填充
14
if (left < max) {
15
helper(left + 1, right, max, `${str}(`);
16
}
17
// 保证两类括号数目一致
18
if (left > right) {
19
helper(left, right + 1, max, `${str})`);
20
}
21
}
22
helper(0, 0, n, '');
23
return res;
24
};
Copied!
复杂度分析
本方法也是使用回溯法,只是具体实现方式不同,因此,复杂度也是一样的。
  • 时间复杂度:
    O(4nn)O(\dfrac{4^n}{\sqrt{n}})
在回溯过程中,每个有效序列最多需要
nn
步。
  • 空间复杂度:
    O(4nn)O(\dfrac{4^n}{\sqrt{n}})
如上所述,并使用
O(n)O(n)
的空间来存储序列。

子集

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例
1
输入: nums = [1,2,3]
2
输出:
3
[
4
[3],
5
[1],
6
[2],
7
[1,2,3],
8
[1,3],
9
[2,3],
10
[1,2],
11
[]
12
]
Copied!

方法一 回溯算法

思路

设置初始二维数组[[]],依次把每个数加入到数组中的每一个元素中,并保留原来的所有元素。

详解

  1. 1.
    初始化二维数组来存储所有子集;
  2. 2.
    使用双层遍历,外层遍历 nums 数组,内层遍历二维数组,将每个元素与二维数组每项合并,并保留二维数组原有的元素
  3. 3.
    并将得到的新子集与二维数组元素合并,最后得到所有子集;
例如:输入 nums = [1, 2, 3] 初始化二维数组存储所有子集 result = [[]] 然后遍历 nums, 1 添加到[], 结果为 [[], [1]]; 2 添加到[], [1], 结果为 [[], [1], [2], [1, 2]]; 3 添加到[], [1], [2], [1, 2], 结果为 [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]];

代码

1
const subsets = (nums) => {
2
let result = [[]]; // 初始化二维数组
3
for (let i of nums) {
4
const temp = [];
5
for (let k of result) {
6
temp.push(k.concat(i)); // 依次把每个元素添加到数组中
7
}
8
result = result.concat(temp);
9
}
10
return result;
11
}
Copied!

复杂度分析

  • 时间复杂度:
    O(2n)O(2^n)
根据上述算法,每次循环 result 数组的次数为
2(n1)2^{(n - 1)}
, 则计算总数为
1+21+22+...+2(n1)1 + 2^1 + 2^2 + ... + 2^{(n-1)}
,根据等比数列计算公式得到循环总次数为
2n12^n - 1
,所以时间复杂度为
O(2n)O(2^n)
  • 空间复杂度:
    O(2n)O(2^n)
根据排列组合原理,子集包含一个数字的情况所耗费的存储空间为
Cn11C_n^1 * 1
,包含两个数字所耗费的存储空间为
Cn22C_n^2 * 2
,根据算法得出 共需要
Cn0+Cn1+2Cn2+...+(n1)Cnn1+nCnnC_n^0 + C_n^1 + 2 * C_n^2 + ... + (n - 1) * C_n^{n - 1} + n * C_n^n
个存储空间,根据排列组合公式求和可得需要
n2n1+1n*2^{n-1} + 1
个额外存储空间, 所以算法空间复杂度为
O(2n)O(2^n)

方法二 二进制表示法

思路

从数学角度看,求子集其实是一个排列组合问题,比如 nums = [1, 2, 3],存在四种情况:
  1. 1.
    都不选,情况共有
    C30=1C_3^0= 1
  2. 2.
    只选 1 个数,情况共有
    C31=3C_3^1 = 3
  3. 3.
    选 2 个数,情况共有
    C32=3C_3^2 = 3
  4. 4.
    全选,情况共有
    C33=1C_3^3 = 1
落到数组中的每个数字,都有两种可能,选与不选,我们用 1 标识选,用 0 标识不选。 则 [] 表示为 000,[1, 2, 3] 表示为 111,我们通过转化为二进制表示法,遍历 000 - 111 的所有组合,即可求出所有子集。
详解
  1. 1.
    根据上述分析,我们得出加入数组为 nums,则针对每位存在选与不选两种情况,那么所有组合数为
    2length 2 ^ {length}
    个。
  2. 2.
    针对每一种组合情况,我们可以取出该二进制表示法中的每一位,如 110,我们分别通过向右移位并和 1 求与,判断最低为的值为 0 或者 1。
  3. 3.
    如果得到结果为 1,那么表示该位表示的数字在原数组中被选中,存入暂存数组,一轮遍历后即可获得该组子集的数字组合。将所有子集数字组合一起存入结果数组,即求出所有子集。
代码
1
const subsets = (nums) => {
2
// 子集的数量
3
const len = nums.length;
4
const setNums = Math.pow(2, len);
5
const result = [];
6
7
for (let i = 0; i < setNums; i++) {
8
let temp = [];
9
// 判断该二进制表示法中,每一个位是否存在
10
for (let j = 0; j < len; j++) {
11
if (1 & (i >> j)) { // 如果该位为 1,则存入组合数组
12
temp.push(nums[j]);
13
}
14
}
15
16
result.push(temp);
17
}
18
19
return result;
20
};
Copied!
复杂度分析
  • 时间复杂度:
    O(2n)O(2^n)
一共包含
2n2^n
个组合需要
n2nn * 2^n
次计算,所以时间复杂度为
O(2n)O(2^n)
  • 空间复杂度:
    O(2n)O(2^n)

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例
1
输入:"23"
2
3
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
4
![img](https://assets.leetcode-cn.com/aliyun-lc-upload/original_images/17_telephone_keypad.png)
Copied!

方法一 挨个遍历

思路
利用队列的先进先出的特点,把队列中的第一个元素拿出,再与后面的挨个拼接
a, b, c --> b, c, ad, ae, af --> c, ad, ae, af, bd, be, bf -> ...
详解
  1. 1.
    先在队列中插入一个空字符
  2. 2.
    取出队列中的第一个元素,与后一位数字对应的字符进行挨个拼接
  3. 3.
    重复第二步,直到结束
代码
1
const letterCombinations = function (digits) {
2
const map = {
3
2: ['a', 'b', 'c'],
4
3: ['d', 'e', 'f'],
5
4: ['g', 'h', 'i'],
6
5: ['j', 'k', 'l'],
7
6: ['m', 'n', 'o'],
8
7: ['p', 'q', 'r', 's'],
9
8: ['t', 'u', 'v'],
10
9: ['w', 'x', 'y', 'z']
11
};
12
13
if (!digits) {
14
return [];
15
}
16
17
const res = [''];
18
for (let i = 0; i < digits.length; i++) {
19
const letters = map[digits[i]];
20
const size = res.length;
21
for (let j = 0; j < size; j++) {
22
const temp = res.shift(0); // 取出第一个元素
23
for (let k = 0; k < letters.length; k++) {
24
res.push(`${temp}${letters[k]}`); // 第一个元素与后一位数字对应的字符进行挨个拼接
25
}
26
}
27
}
28
return res;
29
};
Copied!
复杂度分析
  • 时间复杂度:
    O(3m4n)O(3^m * 4^n)
    通过数组的 push 我们发现,循环的次数和最后数组的长度是一样的,然而数组的长度有和输入多个3个字母的数目、4个字母的数目有关,得出时间复杂度为
    O(3m4n)O(3^m * 4^n)
    其中
    mm
    为3个字母的数目,
    nn
    为4个字母的数目
  • 空间复杂度:
    O(3m4n)O(3^m * 4^n)
    最后结果的长度和输入的数字有关,得出复杂度为
    O(3m4n)O(3^m * 4^n)

方法二 回溯

思路
这道题有点排列组合的味道,我们可以穷举所有的可能性,找到所有的可能性
详解
  1. 1.
    如果还有数字需要被输入,就继续遍历数字对应的字母进行组合 prefix + letter
  2. 2.
    当发现没有数字输入时,说明已经走完了,得到结果
    代码
1
const map = {
2
2: ['a', 'b', 'c'],
3
3: ['d', 'e', 'f'],
4
4: ['g', 'h', 'i'],
5
5: ['j', 'k', 'l'],
6
6: ['m', 'n', 'o'],
7
7: ['p', 'q', 'r', 's'],
8
8: ['t', 'u', 'v'],
9
9: ['w', 'x', 'y', 'z']
10
};
11
12
const letterCombinations = function (digits) {
13
const result = [];
14
function backtrack (prefix, next) {
15
// 发现没有字母需要输入时,就可以返回了
16
if (next.length === 0) {
17
result.push(prefix);
18
} else {
19
const digit = next[0];
20
const letters = map[digit]; // 获取对应的各个字母
21
for (let i = 0; i < letters.length; i++) {
22
backtrack(prefix + letters[i], next.substr(1));
23
}
24
}
25
}
26
if (digits.length !== 0) {
27
backtrack('', digits);
28
}
29
return result;
30
};
Copied!
复杂度分析
  • 时间复杂度:
    O(3m4n)O(3^m * 4^n)
  • 空间复杂度:
    O(3m4n)O(3^m * 4^n)
最近更新 1yr ago