最近入坑了leetcode,准备好好向葱娘学习学写算法。准备碰到好的一些算法就在这里记录一下。
这里要讲的是第三题，Longest Substring, 一个很简单的题目了，但是发现了一个很精简的做法。
题目如下：
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.
基本思想其实应该很简单了：
一般都是通过Sliding window的做法来写：即用一个变量存子串的最长的长度，然后一个个从左往右移动，因为题目简单就不放做法了。
这里有个很简单的写法：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
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;
}
};
感觉特别简介清晰。
它通过一个vector其实是实现了一个mapping操作，用vector的下标来对应字母，然后值来对应最后一次出现的index. 这样能够有效解决用STL实现的过程一些繁琐的问题（比如如果你使用Map或者Set来存储数据的话，删除的过程会很繁琐。）
语言不够很好描述，代码大家慢慢体会～
