過濾字謎
重要性:4
字謎是指由相同數量相同字母組成的字詞,但字母順序不同。
例如
nap - pan
ear - are - era
cheaters - hectares - teachers
撰寫一個函式 aclean(arr)
,傳回一個已清除字謎的陣列。
例如
let arr = ["nap", "teachers", "cheaters", "PAN", "ear", "era", "hectares"];
alert( aclean(arr) ); // "nap,teachers,ear" or "PAN,cheaters,era"
每個字謎群組應只保留一個字詞,不論哪一個。
若要找出所有字謎,我們將每個字詞拆成字母並對其排序。經過字母排序後,所有字謎都會相同。
例如
nap, pan -> anp
ear, era, are -> aer
cheaters, hectares, teachers -> aceehrst
...
我們將使用字母排序的變體作為對應鍵,以每個鍵只儲存一個值
function aclean(arr) {
let map = new Map();
for (let word of arr) {
// split the word by letters, sort them and join back
let sorted = word.toLowerCase().split('').sort().join(''); // (*)
map.set(sorted, word);
}
return Array.from(map.values());
}
let arr = ["nap", "teachers", "cheaters", "PAN", "ear", "era", "hectares"];
alert( aclean(arr) );
字母排序是由 (*)
行中的呼叫鏈完成的。
為了方便起見,我們將其拆分成多行
let sorted = word // PAN
.toLowerCase() // pan
.split('') // ['p','a','n']
.sort() // ['a','n','p']
.join(''); // anp
兩個不同的字詞 'PAN'
和 'nap'
會得到相同的字母排序形式 'anp'
。
下一行將字詞放入地圖中
map.set(sorted, word);
如果我們再次遇到一個具有相同字母排序形式的字詞,那麼它將使用地圖中具有相同金鑰的先前值覆寫它。因此,我們始終會在每個字母形式中最多只有一個字詞。
最後,Array.from(map.values())
會對地圖值進行可迭代處理(我們不需要結果中的金鑰),並傳回它們的陣列。
在這裡,我們也可以使用純粹的物件,而不是 Map
,因為金鑰是字串。
這就是解決方案的外觀
function aclean(arr) {
let obj = {};
for (let i = 0; i < arr.length; i++) {
let sorted = arr[i].toLowerCase().split("").sort().join("");
obj[sorted] = arr[i];
}
return Object.values(obj);
}
let arr = ["nap", "teachers", "cheaters", "PAN", "ear", "era", "hectares"];
alert( aclean(arr) );