首页 > 代码库 > [LeetCode]3. Longest Substring Without Repeating Characters

[LeetCode]3. Longest Substring Without Repeating Characters

2024-10-13 15:53:39   213人阅读

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.
 
给定一个字符串，找到它最长的子串，在子串内不会出现相同的字符。
例如：
对于 "abcababb"，它的最长子串是 "abc"，长度为3。
对于 "bbbbb" ，它的最长子串是 "b"，长度为1。
对于 "pwwkew" ，它的最长子串是 "wke" ，长度为3。
 
思路一：用双重循环，记录遇到的值到set，在遍历过程中查找字符是否存在set中，存在说明不符条件。 
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLength=0,curLength=0;
        set<char> dict;            
        for(int i=0;i<s.size();++i){
            curLength=0;                                     
            for(int j=i;j<s.size();++j){
                if(dict.find(s[j])!=dict.end()){      //在set查找当前值是否出现过
                    break;
                }
                else{
                    ++curLength;                       //子串当前长度
                    dict.insert(s[j]);                 //没有出现就插入到set中
                }
            }
            if(curLength>maxLength)maxLength=curLength;
            dict.clear();
        }
        return maxLength;
    }
};

思路二：

字符串中一共有256个字符，为每个字符设置一个索引表示字符出现的位置，字符初始值都是-1，子串的开始位置start也是-1。
按字符串顺序遍历字符串，
若遇到的都是不同的字符，字符的索引值递增并计算此时与start的距离，如果大于maxLength就更新maxLength的值
若遇到相同的字符串，此时字符索引值必然大于start并且因为破坏了规则，那下一个start的位置就向前移动到上一次该字符位置。
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> dict(256,-1);       //每个出现的字符位置
        int maxLength=0,start=-1;
        for(int i=0;i<s.size();++i){
            if(dict[s[i]]>start){       //如果当前字符位置大于start，说明当前这个子串遇到了这个字符两次
                start=dict[s[i]];       //那么start就移动到在这个子串中这个字符第一次出现的位置 作为寻找下一个子串的起点
            }
            dict[s[i]]=i;               //更新当前字符的位置
            maxLength=max(maxLength,i-start); //长度出现较大值 更新它
        }
        return maxLength;
    }
};

 

 

[LeetCode]3. Longest Substring Without Repeating Characters


联系
我们