问题
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 subsequenceand not a substring.
分析
首先,这种题肯定不能暴力来解决,否则肯定会超时。所以,考虑用一个哈希表(Map<char, int>)来维护状态。key是字符,value是当前字符出现在字符串的位置。
可能有个疑问,为什么这道题归类到“动态规划”中。动态规划类题目中的一共特性就是要有一个状态转移方程,可是这道题直接看起来并没有。但其实,思想是相同通。即当前状态的解要根据之前上一状态的信息来求解。只不过求解的过程不能用一个状态转移方程来解决,所以我认为这道题也有着动态规划的思想。
时间复杂度
O(n)
代码
[code lang=”cpp”]
/**
* https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description
*
* dp
*/
#include <iostream>
#include <vector>
#include
<map>
#include <string>
using namespace std;
#define MAX 1000000001
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char, int> dp;
int max_length = -1, cur_length = 0, cur_offset = 0, length = s.size(), last_offset = 0;
for (int i = 1; i < length + 1; ++i) {
map<char, int>::iterator it = dp.find(s[i – 1]);
if (it != dp.end() && it->second >= cur_offset) {
last_offset = it->second;
cur_offset = last_offset + 1;
cur_length = i – cur_offset + 1;
} else {
if (++cur_length > max_length) max_length = cur_length;
dp.insert(pair<char, int>(s[i – 1], i));
}
it->second = i;// re-write the current pos for the cur char
}
return max_length > 0 ? max_length : 0;
}
};
int main(int argc, char * argv[]) {
Solution * s = new Solution();
cout<<s->lengthOfLongestSubstring("qwnfenpglqdq");
}
[/code]
问题来源:https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description
谢谢,用到了~~~~~~~~~~~~~~~~~~~~