文字列の配列から文字列を完成させるために部分文字列を一致させる

Question

これは私が一度尋ねた質問の小さな部分です。

入力リスト[] =私は[] = {ABCD、XYZW、QWER、ABCDE}

そして、私の入力がある

STRリストのような文字列の変数配列を有します{AB、ABC、Q、Z、X}

出力すべきである[] = {ABCD、ABCD、QWER、 - 、XYZW}

各入力文字列は、リストの同じ文字（最初から）と一致する必要があります。それは答えとして最初に利用可能な文字列を与えるべきです。

作業私がいたと考えることができ近づい： -

1. ブルートフォース：時間の複雑性O（リスト内の文字列の（数）*（入力文字列の平均長）*（入力の数文字列））

2. ハッシング：同じ時間もかかります。

これを行うより良い方法はありますか？

Answer 1

あなたのリスト[]が修正されている（またはあまり変更されていない）場合、トライがそのトリックを行います。挿入中は、 "最初の一致"を識別するために少しのロジックを実行する必要があります。 "abcd"が最初の場合は、 "abcde"を挿入しないでください（無効にしてください。会計と簿記のビットを行う必要があります）。

詳細：私が正しくあなたの意図を理解し、少なくとも場合http://en.wikipedia.org/wiki/Trie