root;
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
1.拆分时可以重复使用字典中的单词。
2.你可以假设字典中没有重复的单词。
Example
example1
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意: 你可以重复使用字典中的单词。
example2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
动态规划的关键点是：
寻找状态转移方程
有了这个状态转移方程，我们就可以根据上一阶段状态和决策结果，去求出本阶段的状态和结果
然后，就可以从初始值，不断递推求出最终结果。
在这个问题里，我们使用一个一维数组来存放动态规划过程的递推数据
假设这个数组为dp，数组元素都为true或者false,
dp[N] 存放的是字符串s中从0到N截取的子串是否是“可拆分”的布尔值
让我们从一个具体的中间场景出发来思考计算过程
假设我们有
wordDict = ['ab','cd','ef']
s ='abcdef'
并且假设目前我们已经得出了N=1到N=5的情况，而现在需要计算N=6的情况
或者说，我们已经求出了dp[1] 到dp[5]的布尔值，现在需要计算dp[6] = ?
该怎么计算呢？
现在新的字符f被加入到序列“abcde”的后面，如此以来，就新增了以下几种6种需要计算的情况
A序列 + B序列
1.abcdef + ""
2.abcde + f
3.abcd + ef
4.abc + def
5.ab + cdef
6.a + bcdef
注意：当A可拆且B可拆时，则A+B也是可拆分的
从中我们不难发现两点
当A可拆且B可拆时，则A+B也是可拆分的
这6种情况只要有一种组合序列是可拆分的，abcdef就一定是可拆的，也就得出dp[6] = true了
下面是根据根据已有的dp[1] 到dp[5]的布尔值，动态计算dp[6] 的过程
var
wordBreak =
function
(s, wordDict) {
//
处理空字符串
if
(s === '' && wordDict.indexOf ('') === -1
) {
return
false
;
const len
=
s.length;
//
默认初始值全部为false
const dp =
initDp (len);
const a
= s.charAt (0
);
//
初始化动态规划的初始值
dp[0] = wordDict.indexOf (a) === -1 ?
false
:
true
;
dp[
1] = wordDict.indexOf (a) === -1 ?
false
:
true
;
//
i:end
//
j:start
for
(let i = 1; i < len; i++
) {
for
(let j = 0; j <= i; j++
) {
//
序列[0,i] = 序列[0,j] + 序列[j,i]
//
preCanBreak表示序列[0,j]是否是可拆分的
const preCanBreak =
dp[j];
//
截取序列[j,i]
const str = s.slice (j, i + 1
);
//
curCanBreak表示序列[j,i]是否是可拆分的
const curCanBreak = wordDict.indexOf (str) !== -1
;
//
情况1: 序列[0,j]和序列[j,i]都可拆分，那么序列[0,i]肯定也是可拆分的
const flag1 = preCanBreak &&
curCanBreak;
//
情况2: 序列[0,i]本身就存在于字典中，所以是可拆分的
const flag2 = curCanBreak && j === 0
;
if
(flag1 ||
flag2) {
//
设置bool值，本轮计算结束
dp[i + 1] =
true
;
break
;
//
返回最后结果
return
dp[len];
给定一个
没有重复
数字的序列，返回其所有可能的全排列。
Example
输入: [1,2,3]
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
深度优先搜索搞一波，index在递归中向前推进
当index等于数组长度的时候，结束递归，收集到results中（数组记得要深拷贝哦）
两次数字交换的运用，计算出两种情况
想不通没关系，套路一波就完事了
var swap = function (nums, i, j) {
const temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
var recursion = function (nums, results, index) {
// 剪枝
if (index >= nums.length) {
results.push (nums.concat ());
return;
// 初始化i为index
for (let i = index; i < nums.length; i++) {
// index 和 i交换？？
// 统计交换和没交换的两种情况
swap (nums, index, i);
recursion (nums, results, index + 1);
swap (nums, index, i);
* @param {number[]} nums
* @return {number[][]}
var permute = function (nums) {
const results = [];
recursion (nums, results, 0);
return results;
