# [競程] 文件的碎片

###### tags: `競程`

* Online Judge: [10132](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1073)

## 題目
有幾個相同的文件，很不幸地都被損壞了，每個文件都被隨機從中切成兩半。給定這些文件的碎片fragments（順序隨機），我們需要復原這些檔案的內容。

這些文件為只包含有0和1的字串。

## 範例

輸入: fragments = ["011", "0111", "01110", "111", "0111", "10111"]
輸出: "01110111"

## 思路
在這邊我們注意到以下幾點：
* 每個文件都剛好被分成兩半，所以在碎片中**最短字串的長度**加上**最長字串的長度**就會剛好是**原始字串的長度**，我們用`length`表示。
* 已知文件的長度，從第一個字串開始，讓它和後面的字串相匹配（而不必和前面的字串匹配），只要相加起來長度是`length`即可。
* A和B兩個字串連接的方式有兩種可能：AB和BA。對於字串A，可以把這兩種情況全部放進dict裡面，其中key是字串A，value是一個 list`[AB, BA]`。這邊我們選用`defaultdict(list)`，這樣就可以直接append字串上去。
* 最後我們再對那些出現在values的字串進行統計，出現最多次的就是答案。

## 解答

from collections import defaultdict, Counter

def file_fragments(fragments):
    lens = [len(s) for s in fragments]
    length = min(lens) + max(lens)
    results = defaultdict(list)
    for i, s in enumerate(fragments):
        for j in range(i + 1, len(fragments)):
            if len(s) + len(fragments[j]) == length:
                results[s].append(s + fragments[j])
                results[s].append(fragments[j] + s)
    words = []
    for row in results.values():
        for s in row:
            words.append(s)
    return max(words, key = words.count)