Browsed by
Month: June 2015

Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1. 做这道题时,脑袋里面不停的想起DP的声音,无奈,当时学算法时,DP就是一个弱项,而自己做这题时,又不停的往这个方向去想,所以一直都没有解答出来,最后还是靠这篇文章才找到解决方法而过关。 基本上,第一个直观到思路就是从第一个字符开始向后找,如果不是重复的,就加入到hash表中,然后向后继续找,直到重复时,比较是否是最长的,然后纪录下长度,清空hash表,继续找到最后一个字符为止;接着从第二个字符开始,依次找到每个字符到最后一个字符中所有的不重复字串,这个就是暴力法了。 第二个思路是,其实不需要每个字符都一遍遍寻找,比如abcabc,那么找到abc后,下一个字符a就跟abc中到a重复,然后记下长度,接着从bca组成到新字符串开始向后寻找,也就是从index为1的字符串重新开始找,这样就比第一个方法节省一些时间了。 可是还是不够快,因为从上次重复的下一个字符开始找,还是需要清除map并且重新找,其实可以上一次重复的位置纪录下来,然后只要清除那之前的字符就可以了。 代码如下 int lengthOfLongestSubstring(string s) { int maxLength = 0; int lastRepeatCharIndex = 0; unordered_set uniqueSubStrings; for( int i = 0; i < s.length(); i++ ) { char c = s[i]; if(uniqueSubStrings.find(c) == uniqueSubStrings.end()) {…

Read More Read More