アナグラムのフィルタリング
importanza: 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
...
文字でソートされたバリアントは、キーとしてマップに使用して、各キーに1つの値だけを格納します。
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
2つの異なる単語'PAN'
と'nap'
は同じ文字でソートされた形式'anp'
を受け取ります。
次の行は単語をマップに配置します
map.
set
(
sorted,
word)
;
同じ文字でソートされた形式の単語をもう一度見つけた場合、マップ内の同じキーを持つ前の値が上書きされます。そのため、文字形式ごとに単語が1つだけ残ります。
最後に、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)
)
;