Catalog
  1. 1. 3. Longest Substring Without Repeating Characters
LeetCode Solution: 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: “bbbbb”
Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: “pwwkew”
Output: 3

Explanation: 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.

解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
std::string ans;
std::string temp;
for (auto i = 0; i < s.size(); ++i) {
if (ans.empty())
ans += s.at(i);
else if (ans.find(s.at(i)) != std::string::npos) {
temp = ans.size() > temp.size() ? ans : temp;
ans.erase(ans.begin(),
ans.begin() + ans.find(s.at(i)) + 1);
ans += s.at(i);
}
else if (ans.find(s.at(i)) == std::string::npos)
ans.push_back(s.at(i));
}
ans = temp.length() > ans.length() ? temp : ans;
return ans.size();
}
};

题目要求寻找最小的子字符串,可以运用滑动窗口的思想

对原始字符串每一个字符进行遍历

  1. 如果目标子串为空,把该字符放入目标子串
  2. 如果在目标子串中找到了当前遍历的字符,将临时字符串赋值为anstemp中较长的那一个,并删除掉目标子串中目标字符的重复元素及其之前的所有字符
    eg: s="aababc" ans="ab" i=3
    此时i=3及表示源字符串的 'a' 在目标字符串中出现了,所以删除掉目标字符串中'b'以及'a'之前的所有字符,并把当前的'a'加入字符串中,相当于将原窗口s="a[ab]abc"向右滑动为s="aa[ba]bc"
    即表示向右滑动的字符个数为s.at(i)ans中出现的索引
    如上所示,'a'出现在ans中的第一位,所以将窗口向右滑动一个单位
  3. 如果在目标子串中没有找到该字符,就将窗口向右扩展一位
    eg: s="aab[ab]c"在下一步进行时变为s="aab[abc]"向右扩展一位

ps:temp = ans.size() > temp.size() ? ans : temp;这一步是为了防止当`ans``寻找到最后一个字符串时,发现却是比上一个字符串还小的字符串

算法缺陷:
表面上是滑动窗口,实际在源字符串中将当前字符串不断与之前的字符串进行比较,寻找一个最大的字符串

时间复杂度O(m*n)

Author: Jsthcit
Link: http://jsthcitpizifly.com/2019/10/26/LeetCode-Solution-3/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶

Comment