[LeetCode]HashTable主题系列{第3题}

昊楠Hacking

发布于 2018-03-30 10:24:26

9510

1. 内容介绍

开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程，具体内容层次按照{题目，分析，初解，初解结果，优化解，优化解结果，反思}的格式来记录，供日后复习和反思[注：有些题目的解法比较单一，就没有优化过程]。题目的顺序按照leetcode给出的题目顺序，有些题目在并不是按照题目本身序号顺序排列的，也不是严格按照难易程度来排列的。

因此，这篇文章并不具有很强的归类总结性，归类总结性知识将会在其他文章记录，本篇重点在记录解题过程中的思路，希望能对自己有所启发。

2. 题目和解题过程

2.1 Longest Substring Without Repeating Characters

题目：Given a string, find the length of the longest substring without repeating characters.Examples:Given "abcabcbb", the answer is "abc", which the length is 3.Given "bbbbb", the answer is "b", with the length of 1.Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
分析：题目点明了三个要素：子串，无重复字符，最长。其中子串意味着选取的字符串在源字符串中是连续存在的，无重复和最长是自明的。题目的难点之一是对于一个字符，如何在现有子串中快速判重，显然，遍历搜索时间复杂度是O(n)，红黑树set查询的时间复杂度是O(logn)，而哈希表unordered_set拥有最快速的速度，其时间复杂度是O(1)。以下先给出一个暴力解法，便于理清基本思路和观察可以优化的地方，同时也方便拿时间和优化解法的时间进行对比，凸显算法设计的重要性。
初解：先从源字符串S头部第一个字符开始，向后连续生成子串，对于每一个后续的字符进行判重，如果重复则记录下当前子串长度和内容，然后移动到第二个字符重复之前的过程，依次类推，直到源字符串的最后一个字符。其中如果遇到比当前最长无重复子串长度更长的子串，则更新此记录。该解法的时间复杂度约为O(n2)。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        string longest_substr="";
        for(int index=0; index < s.size(); ++index)
        {
            set<char> char_set;
            string tmp_substr = "";
            find_longest_substr(s, index, char_set, tmp_substr);
            if(tmp_substr.size() > longest_substr.size())
                longest_substr = tmp_substr;
        }
        return longest_substr.size();
    }
    void find_longest_substr(string& s, int index, set<char>& char_set, string& tmp_substr)
    {
        for(int start = index; start < s.size(); ++start)
        {
            if(char_set.find(s[start])==char_set.end())
            {
                char_set.insert(s[start]);
                tmp_substr+=s[start];
            }
            else break;
        }
    }
};

初解结果：

优化解法1：初解中每次遇到重复字符时，重新从当前起始字符的下一个字符开始搜索，这样会做额外的无用功，因为例如字符串abcdad，从a开始搜索时a字符重复但是中间字符串bcd并未重复，因此可以不必重新从b开始搜索，而是将首部的a去掉直接从bcda后的d开始继续搜索。根据上面的例子可以总结出一个规律：当出现重复字符时，只需要将该字符在子串中重复的位置以前的字符去除掉，然后判断当前剩余的字符长度加上现有子串长度之和小于当前计算出来的最长子串长度时，可以终止搜索了，否则继续沿着当前搜索的位置向后搜索，直到源字符串结尾。此处的优化思想是从现有结果中提取无需重复计算的结果，节省计算时间，减少总体重复计算的总量。至于查重方法，暂时使用红黑树实现的set。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() <= 1) 
            return s.size();
        int length = 0, last_pos = 0;
        set<char> substring;
        for(int i = 0; i < s.size(); ++i)
            find_longest_substr(s, i, substring, last_pos, length);
        if(length < substring.size())
            length = substring.size();
        return length;
    }
    void find_longest_substr(string& s, int& index, set<char>& substring, int& last_pos, int& length)
    {
        if(substring.find(s[index]) == substring.end())
            substring.insert(s[index]);
        else
            erase_duplicate_subsubstring(s, index, substring, last_pos, length);
    }
    void erase_duplicate_subsubstring(string& s, int& index, set<char>& substring, int& last_pos, int& length)
    {
        if(length < substring.size())
            length = substring.size();
        for(int j = last_pos; j < index; ++j)
        {
            substring.erase(s[j]);
            if(s[j]==s[index])
            {
                last_pos = j+1;
                break;
            }
        }
        substring.insert(s[index]);
    }
};

优化结果1：

优化解法2：将查重方式改为哈希表unordered_set。
优化结果2：结果差别不大，不予展示。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

[LeetCode]HashTable主题系列{第3题}

[LeetCode]HashTable主题系列{第3题}

1. 内容介绍

2. 题目和解题过程

2.1 Longest Substring Without Repeating Characters

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐