存档

文章标签 ‘hash’

最长不重复子串

2012年6月25日 20 条评论

---

题:从一个字符串中找到一个连续子串,该子串中任何两个字符不能相同,求子串的最大长度并输出一条最长不重复子串。

本节从最直接的方法逐步优化,渐进探索了四种实现方式,并最终找到时间复杂度为O(N),辅助空间为常数的方案,内容如下:

==基本算法 使用Hash==

==DP方案==

==DP + Hash 方案==

==DP + Hash 优化方案==

==================================

基本算法 使用Hash

要求子串中的字符不能重复,判重问题首先想到的就是hash,寻找满足要求的子串,最直接的方法就是遍历每个字符起始的子串,辅助hash,寻求最长的不重复子串,由于要遍历每个子串故复杂度为O(n^2),n为字符串的长度,辅助的空间为常数hash[256]。代码如下:

阅读全文...