# 解 Perl Weekly Challenge 094 -- 異位構詞字群與二元樹轉連結串列

Perl Weekly Challenge 094 題目又出現二元樹了。那麼就來沿用上一回解答中所定義的 `IntBinaryTree` 吧。

## TASK #1 › Group Anagrams

Submitted by: Mohammad S Anwar

You are given an array of strings @S.

Write a script to group Anagrams together in any random order.

``````An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
``````

Example 1:

``````Input: ("opt", "bat", "saw", "tab", "pot", "top", "was")
Output: [ ("bat", "tab"),
("saw", "was"),
("top", "pot", "opt") ]
``````

Example 2:

``````Input: ("x")
Output: [ ("x") ]
``````

## 解 #1 › Group Anagrams

Anagram 這個字在 Wikipedia 上譯為「異位構詞字」，雖然好像是個很複雜造詞，但似乎有抓到「異構」這核心精神。姑且沿用。

``````sub is-anagram (Str \$a, Str \$b) {
return False unless \$a.chars == \$b.chars;

return \$a.comb.sort eqv \$b.comb.sort
}``````

1. 從頭開始逐一看過 `@S` 內的字串 `\$s`
2. 逐一檢查目前的分組，看看 `\$s` 是否屬於其中任何一組
1. 如果 `\$s` 屬於某組，則將 \$s 添加至該組
2. 否則，以 `\$s` 為組頭，添加新組

Raku 實作如下。數字標記處表示演算法步驟：

``````sub group-anagrams (@S) {
my %groups;

# [1]
for @S -> \$s {
# [2]
my \$group = %groups.keys.first(-> \$it { is-anagram(\$s, \$it) });

# [2.2]
unless \$group.defined {
\$group = \$s;
%groups{\$group} = [];
}

# [2.1], [2,2]
%groups{\$group}.push(\$s);
}

return %groups;
}
``````

## TASK #2 › Binary Tree to Linked List

Submitted by: Mohammad S Anwar

You are given a binary tree.

Write a script to represent the given binary tree as an object and flatten it to a linked list object. Finally print the linked list object. Example:

``````Input:

1
/ \
2   3
/ \
4   5
/ \
6   7

Output:

1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 3
``````

## 解 #2 › Binary Tree to Linked List

``````class IntBinaryTree {
has IntBinaryTree \$.left-child;
has IntBinaryTree \$.right-child;
}

method set-next (IntLinkedList \$n) {
\$!next = \$n;
}
}``````

``````sub binary-tree-to-linked-list (IntBinaryTree \$tree) {
my \$tail = \$head;

if \$tree.left-child {
my \$sub-list = binary-tree-to-linked-list(\$tree.left-child);
\$tail.set-next: \$sub-list;

while \$tail.next.defined {
\$tail = \$tail.next;
}
}

if \$tree.right-child {
my \$sub-list = binary-tree-to-linked-list(\$tree.right-child);
\$tail.set-next: \$sub-list;

while \$tail.next.defined {
\$tail = \$tail.next;
}
}