【LeetCode(3)】查找最长的不包含重复字符的子串

作者: veaxen 分类: 数据结构与算法,编程题目 发布时间: 2017-05-13 22:14

LeetCode的第3题,给定一个字符串,找到其中的一个最长的字串,使得这个子串不包含重复的字符。

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

我的求解思路是采用数组记录字符是否有出现,因为只有256个字符,所以以空间换取时间相当划算。

使用left和right两个指针进行搜索,left代表候选的最长子串的开头,right代表候选的最长子串的结尾。

先假设left不动,那么在理想的情况下,我们希望可以一直右移right,直到j到达原字符串的结尾,此时right-left就构成了一个候选的最长子串。每次都维护一个max_length,就可以选出最长子串了。

实际情况是,不一定可以一直右移right,如果字符right已经重复出现过(假设在位置k),就需要停止右移了。记录当前的候选子串并和max_length做比较。接下来为下一次搜寻做准备。

在下一次搜寻中,left应该更新到k+1。这句话的意思是,用这个例子来理解,abcdef是个不重复的子串,abcdefc中(为了方便记录为abc1defc2),c1和c2重复了。那么下一次搜寻,应该跨过出现重复的地方进行,否则找出来的候选串依然有重复字符,且长度还不如上次的搜索。所以下一次搜索,直接从c1的下一个字符d开始进行,也就是说,下一次搜寻中,left应该更新到k+1。

我的代码,时间复杂度为O(n):

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        const int slen = s.length();

        int max_len = 0;
        int cur_len = 0;
        int left = 0;
        int right = 0;
        bool exist[256] = {false};

        while(right < slen){

            if(!exist[s[right]]){
                exist[s[right]] = true;
                ++right;
            }else{
                cur_len = right - left;
                if(cur_len > max_len){
                    max_len = cur_len;
                }
                //将left移动到k+1的位置,k就是重复字符所在的位置
                while(s[left] != s[right]){
                    exist[s[left]] = false;//清空k位置之前出现并记录在exist数组中的字母,因为要重新开始查找下一个子串
                    ++left;
                }
                ++left;
                ++right;//已经把right位置的字母记录下了,如果不移动,!exist[s[right]]将一直成立
            }
        }
        //跳出循环之后要记得,这个比较容易忘记
        cur_len = right - left;
        if(cur_len > max_len){
            max_len = cur_len;
        }


        return max_len;
    }
};

看了我的渣渣代码之后,来看看大神的代码,看了LeetCode里的顶级大神是怎么解决这个问题的。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int>v(256,-1);
        int len=s.size(),ans=0,start=-1;

        for(int i=0;i<len;i++){
            if(v[s[i]]>start)//Slding window
                start=v[s[i]];
            v[s[i]]=i;
            ans=max(ans,i-start);
        }
        return ans;
    }
};

代码只能用精辟来形容了,还是以长度为256的数组换取时间,时间复杂度也是O(n),但上面这段代码在运行时间上远胜我写的代码。

大神的思路是,用v数组记录字母出现的位置,start指向本次查找子串的第一个字符的前一个字符(这个start位置的字符就是上次子串查找中,重复出现的那个字符)。
在遍历时,
1. 如果字符s[i]的位置v[s[i]]比start小,那么表明,在start之后的遍历过程中,s[i]还没有出现过,此时重新设置字符s[i]的位置v[s[i]] = i,继续遍历下一个字母;
2. 如果字符si[i]的位置v[s[i]]比start大,那么表明,在start之后的遍历过程中,s[i]已经出现过了,此时将start移动到v[s[i]]位置,并重新设置字符s[i]的位置v[s[i]] = i,继续遍历下一个字母。
重复以上步骤,同时维护ans是最大的,就OK了。

大神就是大神啊,代码简洁,思路奇特,高效,再次表露出崇拜之情 :scream: 。

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.