解 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 上譯為「異位構詞字」，雖然好像是個很複雜造詞，但似乎有抓到「異構」這核心精神。姑且沿用。

首先我們需要個能判斷兩字是否為異位構詞的函式。依定義，若將詞 $a 中字母重新排序過後可得到詞 $b 的話，表示兩詞為彼此之異位構詞字。也就是說，如果兩個異位構詞字各自的字母列表重新以字典順序排序過，就會得到相同的字串。反之，如果兩個字不是彼此的異位構詞字，兩個排序過的字母列表就不會相同。

另外有個很簡單的必要條件：如果兩詞長度不同，則不可能為彼此之異位構詞。

綜合上述兩條件，可得 Raku 實作如下：

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

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

而本題可以用個「邊檢查 @S 一邊分組」的解法：

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

雖然沒有描述得很清楚，不過過從這範例看來，是要以前序走訪全樹。也就是對於每個節點而言，先處理節點自身，接著走訪左子樹，最後走訪右子樹。最終是要把這個走訪過程以連結串列的形式輸出。

先簡單定義二元樹類別 IntBinaryTree 以及連結串列類別 IntLinkedList：

class IntBinaryTree {
    has Int $.payload;
    has IntBinaryTree $.left-child;
    has IntBinaryTree $.right-child;
}

class IntLinkedList {
    has Int $.payload;
    has IntLinkedList $.next;

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

這個演算法的實作可以用遞迴函式解決，Raku 程式碼如下：

sub binary-tree-to-linked-list (IntBinaryTree $tree) {
    my $head = IntLinkedList.new(:payload( $tree.payload ));
    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;
        }
    }

    return $head;
}