c - 将部分字符串匹配到字符串数组中的完整字符串

Question

这是我曾经被问过的一个问题的一小部分。我有一个可变的字符串数组，例如

str list []={abcd,xyzw,qwer,abcde}

我的输入是:

input list[]={ab,abc,q,z,x}

Output should be[]={abcd,abcd,qwer,-,xyzw}

每个输入字符串应与列表中相同的字符(从头开始)匹配。它应该给出第一个可用的字符串作为答案。

我能想到的工作方法是:-

1. 暴力破解:时间复杂度 O((列表中的字符串数量)*(输入字符串的平均长度)*(输入字符串的数量))

2. 哈希:它也花费相同的时间。

有更好的方法吗？

Answer 1

如果你的 list[] 是固定的(或者变化不大)，一个 trie 就可以解决问题。插入时，您必须执行一些逻辑来识别“第一个匹配”，因此如果“abcd”是第一个，则不应插入“abcde”(或者使其无效，如果“abcd”可以被丢弃，那么您必须做一些会计和簿记)。

详情:http://en.wikipedia.org/wiki/Trie