劍指Offer——字元串的排列（JS實作）

題目描述

解題思路

• 這道題屬于考查DFS（深度優先周遊）

*和本道題幾乎完全一樣的有全排列問題，都是在考查DFS

• DFS的本質就是遞歸
• 本題通過設定一個和字元串長度一緻的一維數組，用來表示該元素是否被周遊過，初始值全為false表示都沒有被周遊過
• 當dfs收到的參數的長度和輸入s的長度一緻時，說明一條路徑已經周遊完了，然後開始存儲并傳回

解題代碼

var permutation = function(s) {
    const trace = [];
    const res = [];
    for (let i = 0; i < s.length;i++) {
        trace[i] = false;
    }

    function dfs(str) {
        if (str.length === s.length) {
            res.push(str);
            return;
        }
        for (let i = 0;i < s.length;i++) {
            if (trace[i] === true) continue;
            trace[i] = true;
            dfs(str + s[i]);
            trace[i] = false;
        } 
    }
    dfs('');
    return [...new Set(res)];
};
      

實作效果

總結（本題給我們的啟示思路）

• 啟示一：學會使用DFS
• 啟示二：通過設定一個同緯度的布爾值數組來表示該位置的元素是否被周遊過
• 啟示三；學會通過集合對數組重複元素進行去重