算法题解:从输入string中找出无重复字符的最长子串

发布时间:2019-08-06 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了算法题解:从输入string中找出无重复字符的最长子串脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

题目分析

题目链接:leetcode : Longest Substring Without Repeating Characters

这道题目主要难点在于这样一个问题:
a, b, c, d, e, f, c, g, h, ...
我从第一个字符开始检查,已经检查到f了,目前为止还没有出现重复字符:
[a, b, c, d, e, f,] c, g, h, ...
检查到下一个c时,发现它在前面已经出现过了(至于如何判断新字符是否已经出现过,我们在下面讨论):
[a, b, c, d, e, f, c,] g, h, ...
这时应该怎么办?下一次检查哪个子串?
这时将子串的右端点右移是错误的,因为这样子串中依然包括两个c
[a, b, c, d, e, f, c, g,] h, ...
正确的方式是将子串左端点右移,使它不包含两个成重复的字符:
a, b, c, [d, e, f, c,] g, h, ...
然后再将右端点右移,继续检查:
a, b, c, [d, e, f, c, g,] h, ...

那么如何判断新字符是否已经在子串中出现过呢?
我们可以使用Map<char, bool>,它的原理是:将每个字符作为一个节点存在一颗二叉树中,尝试插入新字符的节点,如果出现冲突(树中已经有相同字符的节点),则表明新字符已经出现过。每次判断的复杂度为LOG(m),m为子串的最大长度。在进行子串左端点右移的时候,要记得将被移出的字符从map种删掉。
还有一种更高效的查找方法:哈希表。在这道题使用哈希表有天然的优势:char的范围是已知的、
较小的——[0, 255](unsigned char)。那么就可以直接用一个bool[256]数组来存储每一种字符是否已出现。在进行子串左端点右移的时候,要记得将被移出的字符重新标记为未访问。

以上两种方法在进行子串左端点右移的时候都要进行重置操作,为了避免它,我们不存储bool(是否出现过),而是存储int(上次出现的下标)。详见下面的代码部分。

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> last_appear_index;
        int sub_string_start = 0, max_length = 0;
        map<char, int>::iterator it;
        for (int i = 0; i < s.length(); i++) {
            it = last_appear_index.find(s[i]);
            if (it != last_appear_index.end() && it->second >= sub_string_start) {
                sub_string_start = it->second+1;
            }
            last_appear_index[s[i]] = i;
            max_length = max(max_length, i-sub_string_start+1);
        }
        return max_length;
    }
};

虽然使用bool[256]更加高效,但是作为算法题,不应该对用户可能输入的字符做任何猜测(在其他语言中,字符可能不用整数表示),使用map<char, int>是更通用的方法。

脚本宝典总结

以上是脚本宝典为你收集整理的算法题解:从输入string中找出无重复字符的最长子串全部内容,希望文章能够帮你解决算法题解:从输入string中找出无重复字符的最长子串所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。