-2

一般的想法是做两个for循环，执行字符串1中的每个字符，比较string2中的每个字符，如果都找到，则表示包含。所以我们需要循环string1中的所有字符，并比较所有字符，看看string2中的所有字符，这将O sqaure运行时间。哪个面试官说这不是个好主意。

在它之后，我正在考虑它。我不能产生一个没有做两个循环的想法。也许我可以先从 string1 中获取所有字符，转换为 asc2，即内置到树中的数字。因此，当与 string2 进行比较时，它会使搜索非常快。

或者任何人有更好的主意？

就像 string1 是 abc 但 string2 是 cbattt 这意味着每个字符都包含在 string2 中。不是子字符串，

4

2 回答 2

1

在文本中搜索给定模式（模式匹配）是一个众所周知的问题。已知解决方案：

  1. KMP
  2. 见证人表
  3. 博耶摩尔
  4. 后缀树

所有解决方案都在一些次要方面有所不同，比如它是否可以推广到 2D 模式匹配，或者更多。如果它需要预处理，如果它可以概括为未绑定的字母，运行时间等'......

编辑：
如果您只想知道某个字符串的所有字母是否都出现在其他字符串中，为什么不使用字母表大小的表格，指示是否可以在字符串中找到给定的字符。如果字母表无界或非常大（超过O(1)），请使用哈希表。

于 2012-10-02T00:18:58.977 回答
1

正如 iccthedral 所说，boyer moore可能是面试官想要的。

于 2012-10-02T00:10:59.047 回答