黑马程序员技术交流社区

标题: 字符串的查找的最快算法的问题 [打印本页]

---

作者: 小城。    时间: 2014-9-26 08:56
标题: 字符串的查找的最快算法的问题
假设这有一个各种字母组成的字符串，假设这还有另外一个字符串，而且这个字符串里的字母数相对少一些。从算法上讲，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？
比如，如果是下面两个字符串：

　　String 1: ABCDEFGHLMNOPQRS

　　String 2: DCGSRQPOM

　　答案是true，所有在string2里的字母string1也都有。如果是下面两个字符串：

　　String 1: ABCDEFGHLMNOPQRS

　　String 2: DCGSRQPOZ

　　答案是false，因为第二个字符串里的Z字母不在第一个字符串里。

---

作者: fantacyleo    时间: 2014-9-26 12:18


我的思路如下：

先把字符串1排序，按你的题意描述，字符串1是固定的，变的是每次与它比较的字符串2，那么实际上这里对字符串1的排序时间复杂度只有O(1)

字符串1一旦排序完毕，后面的查找就是对字符串2的每个字母进行二分查找，由于字符串1固定，每次查找的时间复杂度仍然为O(1)。而字符串2的每个字符都要查一次（正如你的举例，完全可能出现最后一个字符不在字符串1中的情形，故每个字符都要查一次），设字符串2的长度为N，那么整个算法的时间复杂度为排序的O(1)加上查找的N*O(1)，结果是O(N)，即线性复杂度，也就是说字符串2的长度每增加1倍，所需运行时间也翻倍

由于字符串2的每个字符都要查找一次，这证明本题的时间复杂度下界也是O(N)，故以上就是最快算法

---

作者: 谢建平    时间: 2014-9-26 16:55
    楼主去Collection集合 里查个retainsAll方法   会有重大发现哦

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2