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

Question

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

str 列表 []={abcd,xyzw,qwer,abcde}

我的意见是：

输入列表[]={ab,abc,q,z,x}

输出应该是[]={abcd,abcd,qwer,-,xyzw}

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

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

1. 蛮力：时间复杂度O（（列表中的字符串数）*（输入字符串的平均长度）*（输入字符串的数量））

2. 散列：它也需要同样的时间。

有一个更好的方法吗？

Answer 1

如果您的 list[] 已修复（或没有太大变化），则可以使用 trie 来解决问题。在插入时，你必须做一些逻辑来识别“第一个匹配”，所以如果“abcd”是第一个，你不应该插入“abcde”（或者使其无效，如果“abcd”可以被丢弃，所以你必须做一些会计和簿记）。

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