LeetCode #Longest Substring Without Repeating Characters#
思考过么？究竟什么是最长的子字符串
这里有个很要命的概念， 子字符串，别小看这家伙．是搞定题目的关键．
"abcduiwe" 这串字符串是没有重复字符的，那么最长子串就是自己．
但是！一旦出现重复的字符了，当前最大子字符串必然变小．
比方说，，原字符串为＂abcd＂，最大子字符串就是自身．
但这个时候加上了一个字符b
"abcdb"那么这个时候b就作为子串abcd的结束位置了！这就让我们的最大子串（自身），变小了
变成了去除b的前面部分
再看，如果我们加的不同的字符更多
"abcdbefgh"这个时候，最长的子串就是"befgh",要点就在于，从重复的那个字符串开始算新的子字符串！
刚回来的路上还一直闷神，，＂子字符串．．子字符串＂
"""Programmer:EOFe-mail:jasonleaster@gmailDate:2015.04.02File:lswrc.py"""class Solution:# @return an integerdef lengthOfLongestSubstring(self, s):Table = [-1 for i in range(0, 256)]maxLen = 0lastRepeatPos = -1"""We will use @ord() function to translate the characterinto the number of it's ascii code."""for i in range(0, len(s)):if Table[ord(s[i])] != -1 and lastRepeatPos < Table[ord(s[i])]:lastRepeatPos = Table[ord(s[i])]if i – lastRepeatPos > maxLen :maxLen = i – lastRepeatPosTable[ord(s[i])] = ireturn maxLen#———- just for testing ———-s = Solution()print s.lengthOfLongestSubstring("c")print s.lengthOfLongestSubstring("abcdababcde")
下面是 @凯旋冲锋 的java的实现
"""Programmer:EOFe-mail:jasonleaster@gmailDate:2015.04.02File:lswrc.py"""class Solution:# @return an integerdef lengthOfLongestSubstring(self, s):Table = [-1 for i in range(0, 256)]maxLen = 0lastRepeatPos = -1"""We will use @ord() function to translate the characterinto the number of it's ascii code."""for i in range(0, len(s)):if Table[ord(s[i])] != -1 and lastRepeatPos < Table[ord(s[i])]:lastRepeatPos = Table[ord(s[i])]if i – lastRepeatPos > maxLen :maxLen = i – lastRepeatPosTable[ord(s[i])] = ireturn maxLen#———- just for testing ———-s = Solution()print s.lengthOfLongestSubstring("c")print s.lengthOfLongestSubstring("abcdababcde")
皓神的C++实现：
// Source : https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/// Author : Hao Chen// Date : 2014-07-19/********************************************************************************** * * 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.***********************************************************************************/#include <string.h>#include <iostream>#include <string>#include <map>using namespace std;/* * Idea: * * Using a map store each char's index. * * So, we can be easy to know the when duplication and the previous duplicated char's index. * * Then we can take out the previous duplicated char, and keep tracking the maxiumn length. * */int lengthOfLongestSubstring1(string s) {map<char, int> m;int maxLen = 0;int lastRepeatPos = -1;for(int i=0; i<s.size(); i++){if (m.find(s[i])!=m.end() && lastRepeatPos < m[s[i]]) {lastRepeatPos = m[s[i]];}if ( i – lastRepeatPos > maxLen ){maxLen = i – lastRepeatPos;}m[s[i]] = i;}return maxLen;}//don't use <map>int lengthOfLongestSubstring(string s) {const int MAX_CHARS = 256;int m[MAX_CHARS];memset(m, -1, sizeof(m));int maxLen = 0;int lastRepeatPos = -1;for(int i=0; i<s.size(); i++){if (m[s[i]]!=-1 && lastRepeatPos < m[s[i]]) {lastRepeatPos = m[s[i]];}if ( i – lastRepeatPos > maxLen ){maxLen = i – lastRepeatPos;}m[s[i]] = i;}return maxLen;}int main(int argc, char** argv){string s = "abcabcbb";cout << s << " : " << lengthOfLongestSubstring(s) << endl;s = "bbbbb";cout << s << " : " << lengthOfLongestSubstring(s) << endl;s = "bbabcdb";cout << s << " : " << lengthOfLongestSubstring(s) << endl;if (argc>1){s = argv[1];cout << s << " : " << lengthOfLongestSubstring(s) << endl;}return 0;}
当明知不可挽回，唯一补偿的方法就是怀念，
