題目:
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given"abcabcbb", the answer is"abc", which the length is3.
Given"bbbbb", the answer is"b", with the length of1.
Given"pwwkew", the answer is"wke", with the length of3. Note that the answer must be a substring, >"pwke" is a subsequence and not a substring.題目大意：
給定一個(gè)字符串属铁，找到最長(zhǎng)子字符串的長(zhǎng)度而不重復(fù)字符辐怕。
例子：
給定"abcabcbb"稠氮，答案是"abc"救欧，長(zhǎng)度為3
給定"bbbbb"，答案是"b"汇竭，長(zhǎng)度為1
給定"pwwkew"舒裤，答案是"wke"，長(zhǎng)度為3.請(qǐng)注意檀头，答案必須是子字符串，"pwke"是子序列而不是子字符串
具體實(shí)現(xiàn)
//1：基本的實(shí)現(xiàn)方案
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int pos = 0;
int max_len = 0;
string strstr = "";
string max_str = "";
for (int i = 0; i < s.size(); ++i) {
pos = strstr.find(s[i]);
if (pos != -1) {
if (strstr.size() > max_len) {
max_len = strstr.size();
max_str = strstr;
}
strstr = strstr.substr(pos+1, strstr.size());
}
strstr += s[i];
}
if (strstr.size() > max_len) {
max_len = strstr.size();
max_str = strstr;
}
return max_len;
}
};
// 2：牛逼的解決方案
int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1);
int maxLen = 0, start = -1;
for (int i = 0; i != s.length(); i++) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;
}
