Zero heading: algorithm (Leetode, with mind map + all solutions) 300 questions (17) of the letter combination of telephone numbers
Takeaway:
Title Description
An overview of binary solutions (Mind mapping)
Three total solution
Scheme 1
1) code:
// Backtracking (in plain English, recursion) Backtracking is usually done recursively.
// Tip: Always remember, recursion = recursion exit (in order not to get caught in a loop of wireless recursion) + recursion body (generally changing some parameters after calling the function itself).
// Put the general recursion exit in front and the recursion body in back.
var letterCombinations = function(digits) {
// 1) Define the backtracking function (i.e. recursive function DFS).
const dfs = (index, l, digits, curStr, resArr) = > {
// 1.1) recursive export
if (index >= l) {
resArr.push(curStr);
return;
}
// 1.2) Recursive body
const tempArr = map.get(digits[index]),
tempLength = tempArr.length;
// Core: Backtrace = select + not select.
// The for loop enumerates all possibilities, and then selects tempArr[I] and nothing else.
for (let i = 0; i < tempLength; i++) {
dfs(index + 1, l, digits, curStr + tempArr[i], resArr); }};// 2) State initialization.
const l = digits.length,
map = new Map([['2'['a'.'b'.'c']],
['3'['d'.'e'.'f']],
['4'['g'.'h'.'i']],
['5'['j'.'k'.'l']],
['6'['m'.'n'.'o']],
['7'['p'.'q'.'r'.'s']],
['8'['t'.'u'.'v']],
['9'['w'.'x'.'y'.'z']]]);let index = 0,
curStr = ' ',
resArr = [];
// 3) Call the custom backtracking function (i.e., recursive function DFS).
// 3.1) boundary: "", expected to be [].
// if the if branch is not added, its own output will be [""].
if (l <= 0) {
return [];
}
dfs(index, l, digits, curStr, resArr);
// 4) Return result resArr.
return resArr;
};
Copy the codeScheme 2
1) code:
// Option 2 convert the digits string to a two-dimensional array; Keep iterating to do cartesian product; Returns the final Cartesian accumulation set.
// Technique: "mapping, quantity, repeatability, uniqueness (i.e. number of times), etc." is preferred with hash (JS equivalent to map data structure).
/ / 1) "234" to the [[' a ', 'b', 'c'], [' d ', 'e', 'f'], [' g ', 'h', 'I']]
// 2) Core: iterate over the two-dimensional array, taking cartesian product with the next element.
// 2.1) initializing: newAcc = ['a', 'b', 'c']
// 2.2) newAcc takes the Cartesian product with the next element ['d', 'e', 'f'],
/ / get newAcc = [" AD ", "ae", "af", "bd", "be", "bf", "CD" and "ce", "cf"]
// 2.3) Repeat step 2.2 to do the Cartesian product.
// Get newAcc = ["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh" ,"cdi","ceg","ceh","cei","cfg","cfh","cfi"]
// 3) After traversal, newAcc is returned.
var letterCombinations = function(digits) {
// 1) State initialization.
const l = digits.length,
map = new Map([['2'['a'.'b'.'c']],
['3'['d'.'e'.'f']],
['4'['g'.'h'.'i']],
['5'['j'.'k'.'l']],
['6'['m'.'n'.'o']],
['7'['p'.'q'.'r'.'s']],
['8'['t'.'u'.'v']],
['9'['w'.'x'.'y'.'z']]]);// 2) converts the original digits string into the corresponding two-dimensional array tempArr.
/ / such as "234" to the [[' a ', 'b', 'c'], [' d ', 'e', 'f'], [' g ', 'h', 'I']].
const tempArr = digits.split(' ').map(item= > {
return map.get(item);
});
let newAcc = [];
// 3) Convert tempArr into resArr.
// Tip: Variable one, the reduce method using arrays is preferred.
const resArr = tempArr.reduce((acc, cur, index, item) = > {
// Boundary: if the first element, return item[index].
if (index === 0) {
newAcc = item[index];
return newAcc;
}
const accLength = acc.length,
curLength = cur.length;
// Boundary: reset newAcc to [],
// Continue to concatenate newAcc with current ACC, cur.
newAcc = [];
// 3.1) Core: traverses ACC, cur, and splices newAcc.
for (let i = 0; i < accLength; i++) {
for (let j = 0; j < curLength; j++) { newAcc.push(acc[i] + cur[j]); }}// 3.2) Return the newAcc concatenated by ACC and CUR.
returnnewAcc; } []);// 4) Return result resArr.
return resArr;
}
Copy the code3 solution 3
1) code:
// Scheme 3 is similar to scheme 2 except that reduce is not used.
// Do cartesian product; Returns the final Cartesian accumulation set.
// Technique: "mapping, quantity, repeatability, uniqueness (i.e. number of times), etc." is preferred with hash (JS equivalent to map data structure).
/ / 1) "234" to the [[' a ', 'b', 'c'], [' d ', 'e', 'f'], [' g ', 'h', 'I']]
// 2) Core: iterate over the two-dimensional array, taking cartesian product with the next element.
ResArr = ['a', 'b', 'c']
// 2.2) The current resArr takes the Cartesian product with the next element ['d', 'e', 'f'],
/ / get resArr = [" AD ", "ae", "af", "bd", "be", "bf", "CD" and "ce", "cf"]
// 2.3) Repeat step 2.2 to do the Cartesian product.
// get resArr = ["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh" ,"cdi","ceg","ceh","cei","cfg","cfh","cfi"]
// 3) After traversal, return resArr.
var letterCombinations = function(digits) {
// 1) State initialization.
const l = digits.length,
map = new Map([['2'['a'.'b'.'c']],
['3'['d'.'e'.'f']],
['4'['g'.'h'.'i']],
['5'['j'.'k'.'l']],
['6'['m'.'n'.'o']],
['7'['p'.'q'.'r'.'s']],
['8'['t'.'u'.'v']],
['9'['w'.'x'.'y'.'z']]]);let resArr = [];
// Boundary: if the length is 0, return [] directly.
if (l === 0) {
Return [];
return resArr;
} else {
// If the length is not 0, initialize resArr to map.get(digits[0]); .
resArr = map.get(digits[0]);
}
// 2) traversal.
// Core: do cartesian product continuously, update resArr value.
ResArr = map.get(digits[0]); To start!
for (let i = 1; i < l; i++) {
const tempArr = map.get(digits[i]),
tempArrLength = tempArr.length,
resArrLength = resArr.length;
let newResArr = [];
for (let j = 0; j < resArrLength; j++) {
for (let k = 0; k < tempArrLength; k++) {
newResArr.push(resArr[j] + tempArr[k]);
}
}
resArr = newResArr;
}
// 3) Return the result resArr.
return resArr;
}
Copy the code