把一個字符串中的字符重新排列生成新的字符串,返回新生成的字符串里沒有連續重復字符的字符串個數.連續重復只以單個字符為準
例如, aab 應該返回 2 因為它總共有6中排列 (aab, aab, aba, aba, baa, baa),但是只有兩個 (aba and aba)沒有連續重復的字符 (在本例中是 a).
從網上資料獲得了一些思路,我的代碼:
function permAlone(str) { var arr=str.split(""); var perarr=[]; var begin=0; //創建正則,如果字符串全重復,則直接return 0 var reg = /(.)/1+/g; if(str.match(reg)!==null&&str.match(reg)[0]===str){ return 0; } //用于交換的函數 function swap(idx1,idx2){ var temp=arr[idx1]; arr[idx1]=arr[idx2]; arr[idx2]=temp; } //如果begin到了最后一個字符,可以將這個字符串加入到全排列數組中了 function permall(arr,begin){ if(begin==arr.length-1){ perarr[perarr.length]=arr.join(""); return; } for(var i=0;(i+begin)<arr.length;i++){ swap(begin,begin+i); permall(arr,begin+1); swap(begin,begin+i); } } permall(arr,begin); //返回相鄰不重復的數量 return perarr.filter(function(val) { return !val.match(reg); }).length;}permAlone('aab');首先,把第一個字符和其后面的字符一一交換。
接著,固定第一個字符,求后面所有字符的排列。這個時候我們仍把后面的所有字符分成兩部分:后面字符的第一個字符,以及這個字符之后的所有字符。然后把第一個字符逐一和它后面的字符交換。
去重的全排列就是從第一個數字起每個數分別與它后面非重復出現的數字交換。
以上這篇js-FCC算法-No repeats please字符串的全排列(詳解)就是小編分享給大家的全部內容了,希望能給大家一個參考,也希望大家多多支持武林網。
新聞熱點
疑難解答