編碼面試會(huì)帶來許多可能的挑戰(zhàn)。 不管你喜不喜歡，數(shù)據(jù)結(jié)構(gòu)和算法問題在軟件開發(fā)過程中仍然很常見。 申請(qǐng)足夠多的工作，你很可能會(huì)遇到這樣的問題：
給定一個(gè)字符串，返回該字符串的所有唯一排列
起初看起來很簡(jiǎn)單，但很快就會(huì)發(fā)現(xiàn)隱藏在表面之下的一些復(fù)雜性。 讓我們看看這個(gè)問題是什么，它帶來的挑戰(zhàn)，以及它是如何解決的。
讓我們從了解問題要求的內(nèi)容開始：字符串的所有唯一排列。 排列是事物順序的變化。 關(guān)于這個(gè)問題，排列是一個(gè)包含所有相同字符但順序不同的新字符串。 例如，給定字符串“abc”，排列將是：
“abc”, “acb”, “bac”, “bca”, “cab”, “cba”
期望的結(jié)果是來自給定字符串的所有不同字母組合。讓我們分解問題并解決它。
查看“abc”對(duì)結(jié)果的仔細(xì)檢查表明，不同的組合是通過取一個(gè)字母，將其移到前面，然后將其余字母的不同組合附加到它來實(shí)現(xiàn)的。
以“a”作為前導(dǎo)字母，剩下的兩個(gè)字母“bc”將有兩種可能的組合，“bc”和“cb”，從而產(chǎn)生“abc”和“acb”。
將“b”作為前導(dǎo)字母，其余字母“ac”可以重新排列為“ac”或“ca”，從而產(chǎn)生“bac”和“bca”。
最后，前導(dǎo)字母“c”具有剩余的字母“ab”和“ba”，從而產(chǎn)生“cab”和“cba”。
這種方法可以分解為迭代給定字符串中的每個(gè)字母，將其保存為前導(dǎo)字符，然后迭代剩余的字母以獲得它們的不同組合并將這些組合附加到前導(dǎo)字符。這是很多迭代。在 for 循環(huán)中編寫 for 循環(huán)可能很難閱讀，因此這將是使用遞歸的好時(shí)機(jī)。遞歸是一個(gè)調(diào)用自身直到滿足中斷條件的函數(shù)。
function countdown(n) {
if (n < 1) {
console.log(n);
return
}
console.log(n);
return countdown(n - 1);
}
countdown(5);
// 5
// 4
// 3
// 2
// 1
// 0倒計(jì)時(shí)函數(shù)使用每次調(diào)用減 1 的參數(shù)調(diào)用自身。 這一直持續(xù)到數(shù)字小于 1，函數(shù)返回，遞歸結(jié)束。 這是中斷條件。
回到字符串置換問題，我們將遍歷每個(gè)字符串，獲取當(dāng)前迭代值的字母（我們稱之為 char），然后使用遞歸獲取剩余字母的所有組合，并將它們附加到 char . 結(jié)果將被推入一個(gè)數(shù)組。
function getPermutations(str) {
// break condition to stop recursion
if (str.length < 2) {
return str;
}
// array to store permutations
let permutations = [];
// iterate through string, get char at value i, get remaining letters
for (let i = 0; i < str.length; i++) {
let char = str[i];
let remainingChars = str.slice(0, i) + str.slice(i + 1, str.length);
// use recursion to get all combinations of remainingChars and append them to char
for (let permutation of getPermutations(remainingChars)) {
permutations.push(char + permutation);
}
}
return permutations;
}該函數(shù)以中斷條件開始，因?yàn)槲覀兪褂玫氖沁f歸。 遞歸調(diào)用都使用剩余的字母作為參數(shù)來獲得它們的各種組合。 如果只提供一個(gè)字母（ if(str.length < 2) ），那么只能有一個(gè)組合，因此遞歸停止并返回單個(gè)字母。
接下來我們有一個(gè)數(shù)組（排列）來存儲(chǔ)結(jié)果。
現(xiàn)在遍歷給定的字符串，將 str[i] 處的字母分配給變量 char。 由于我們知道 char 的索引，所以可以使用 slice() 來獲取剩余的字母并將它們分配給剩余的字符。 剩余的字母將用作遞歸函數(shù)調(diào)用中的參數(shù)。
再次使用“abc”，在調(diào)用 getPermutations("abc") 時(shí)，第一次迭代將導(dǎo)致 char = "a" 和 remainingChars = "bc"。 我們現(xiàn)在到達(dá)函數(shù)中的遞歸部分：
for (let permutation of getPermutations(remainingChars)) {
permutations.push(char + permutation);
}for...of 語句遍歷遞歸函數(shù)調(diào)用的每個(gè)返回值，并將它們附加到此時(shí)為“a”的 char 并推送到 permutations 數(shù)組。 剩余字符中的字母當(dāng)前是“bc”，因此第一個(gè)遞歸調(diào)用等同于 getPermutations(“bc”)，它將遍歷這些字母，將它們分開，然后再次遞歸調(diào)用該函數(shù)，直到滿足中斷條件并且我們剩下 “bc”和“cb”被附加到“a”并推送到排列數(shù)組。
這個(gè)過程對(duì)給定字符串中的每個(gè)字母重復(fù)，并產(chǎn)生一個(gè)具有六個(gè)排列的數(shù)組。
let results = getPermutations("abc");
console.log(results);
// ["abc", "acb", "bac", "bca", "cab", "cba"]該功能有效，但必須考慮其他一些事情。 在“abc”示例中，字符串中的每個(gè)字母都是不同的。 如果字符串有重復(fù)字符會(huì)發(fā)生什么？
let results = getPermutations("aab");
console.log(results);
// ["aab", "aba", "aab", "aba", "baa", "baa"]記住問題狀態(tài)以找到所有唯一的排列。 讓我們解決這個(gè)問題。 我們需要一種方法來檢查 char 的當(dāng)前值是否已經(jīng)被使用。 還有其他方法可以完成此操作，但我發(fā)現(xiàn) indexOf() 方法在這里運(yùn)行良好，因?yàn)樗鼨z查給定值的第一個(gè)索引。
for (let i = 0; i < str.length; i++) {
let char = str[i];
if (str.indexOf(char) !== i) {
continue;
}
let remainingChars = str.slice(0, i) + str.slice(i + 1, str.length);
for (let permutation of getPermutations(remainingChars)) {
permutations.push(char + permutation);
}
現(xiàn)在我們有一個(gè)條件來檢查 char 的值是否已經(jīng)被使用過。 如果有，從 indexOf() 返回的索引將低于循環(huán)中的當(dāng)前索引，我們使用 continue 跳到下一次迭代。
let results = getPermutations("zappa");
console.log(results);
/* [
"zappa", "zapap", "zaapp", "zpapa",
"zpaap", "zppaa", "azppa", "azpap",
"azapp", "apzpa", "apzap", "appza",
"appaz", "apazp", "apapz", "aazpp",
"aapzp", "aappz", "pzapa", "pzaap",
"pzpaa", "pazpa", "pazap", "papza",
"papaz", "paazp", "paapz", "ppzaa",
"ppaza", "ppaaz"
]
*/很好，現(xiàn)在每個(gè)排列只出現(xiàn)一次，我們已經(jīng)滿足了問題的要求。 這是所有排列尋找榮耀的完整功能。
function getPermutations(str) {
if (str.length < 2) {
return str;
}
let permutations = [];
for (let i = 0; i < str.length; i++) {
let char = str[i];
if (str.indexOf(char) !== i) {
continue;
}
let remainingChars = str.slice(0, i) + str.slice(i + 1, str.length);
for (let permutation of getPermutations(remainingChars)) {
permutations.push(char + permutation);
}
}
return permutations;
}這個(gè)問題在編程面試中經(jīng)常出現(xiàn)。 僅出于這個(gè)原因?qū)W習(xí)很好，但了解如何解決它也有其他好處。 例如，這是學(xué)習(xí)遞歸以及何時(shí)使用它的好方法。 它還幫助編碼人員注意和解決邊緣情況。 研究它，理解它，然后把你學(xué)到的東西帶到下一個(gè)面試或項(xiàng)目中！
好了，這篇文章的內(nèi)容發(fā)貨聯(lián)盟就和大家分享到這里，如果大家網(wǎng)絡(luò)推廣引流創(chuàng)業(yè)感興趣，可以添加微信：80709525 備注：發(fā)貨聯(lián)盟引流學(xué)習(xí)； 我拉你進(jìn)直播課程學(xué)習(xí)群，每周135晚上都是有實(shí)戰(zhàn)干貨的推廣引流技術(shù)課程免費(fèi)分享！
