偶然看到這樣一個問題:找出字串中出現次數最多的字元。網上多數解法是雙層迴圈,這裡改用遞迴來寫。
/** 取出字符串中重復字數最多的字符 */ var words = 'sdfghjkfastgbyhnvdstyaujskgfdfhlaa'; //創建字符串 var word, //單個字符 length; //該字符的長度 //定義輸出對象 var max = { wordName : '', //重復次數最多的字符 wordLength : 0 //重復的次數 }; //遞歸方法,傳入字符串 (function(words) { if (!words) return; //如果字符串已經變空則返回,結束遞歸 word = words[0]; //取出字符串中的第一個字符 length = words.length; //將length設為當前字符串長度 words = words.replace(new RegExp(word, 'g'), ''); //返回將字符串剔除當前字符的剩余字符串 length = length - words.length; //重設length為當前字符在字符串中的長度 if (length > max.wordLength) //如果該字符重復次數大於maxLength,則重設maxLength為當前字符重復次數 max = { //重設對象的值 wordName : word, wordLength : length }; arguments.callee(words); //遞歸調用,傳入剩余字符串 })(words); console.log(max.wordName+"\n"+max.wordLength); //遞歸結束後輸出結果
每遞迴一次就做四件事:取出第一個字元;用原本的長度減去「剔除所有該字元後的長度」,得到它出現的次數;若這個次數勝過目前記錄,就更新 max;最後對剩下的字串再跑一次,直到字串清空為止。
用長度差算次數很聰明。 length - words.length 一次就得到出現次數,省掉了迴圈計數。
arguments.callee 已不建議使用。 它在嚴格模式下會直接報錯,也妨礙引擎做優化。改成具名函式表達式即可:(function countMax(str){ ... countMax(rest); })(words)。
new RegExp(word, 'g') 有兩個潛在問題。 一是若字元本身是 .、*、?、( 等正則元字元,會造成非預期的比對甚至語法錯誤,必須先 escape;二是 this 版本會把「出現一次」的字元也算進去,若只想找重複的,記得過濾掉 wordLength <= 1 的情況。範例字串裡每個字母都出現多次所以看不出問題。
用一個物件當計數表,一次遍歷就解決,時間複雜度是 O(n),而且不會有遞迴深度或正則的疑慮:
宣告 const map = {},逐一走過字串每個字元,map[ch] = (map[ch] || 0) + 1;再一次 Object.entries(map).sort((a,b) => b[1] - a[1])[0] 就能拿到次數最多的字元與次數。
遞迴版的好處是示範了「用長度差計算重複次數」這個巧思,但真正上 production 時,計數表才是標準答案——更好懂、更快,也不會撞到呼叫堆疊上限。