algorithm - 字符串列表中的字符

Question

早上好

我为发布这个问题感到羞愧，因为我应该能够独自解决这个问题，但目前我想不出任何更好的解决方案......

假设我有一个字符列表 L 和一个字符串 S。我想知道 S 中的每个字符是否都属于 L，目前我唯一想不到的解决方案是微不足道的

boolean Result = true
boolean Temp = false

for i from 1 to S.Length
    Temp <- false
    for j from 1 to A.Count
        if (S[i] == A[j]) Temp <- true

    Result = Result && Temp

return Result

请注意，我不关心优化这个算法，这很容易完成，而是一个更好算法。谁能帮我弄清楚？还要注意，大多数时候 S.Length 比 A.Count 大得多。最后，我不想使用正则表达式。

非常感谢。

Answer 1

这里迭代字符列表的成本为 O(A.Count)。您可以将字符存储在 hash table 中, 因此只要选择适当的散列函数，就可以在常数时间内确定 S[i] 是否属于 A。

因此，通过一个好的哈希函数，您可以将全局成本从 O(S.Length * A.Count) 降低到 O(S.Length)。

如果您正在处理 ASCII 字符，那么您的哈希表可能会被简单地缩减为一个包含 128 个元素的数组，其标识为“哈希函数”。如果您正在处理 Unicode 字符，但您的文本包含大部分 ASCII 字符，那么您可能会想到这种变体。