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.
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
思路：
首先是判断有没有重复，用到Hash方法 – 散列。
然后这里的想法是用一个区间，没有重复就向右增大区间，有重复就右移一位。
这样只要记录最大区间就好了。
区间范围可记为 [end-max,end)
python代码如下…初学，风格不好，见谅。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution(object): def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ #用到的是list生成器 hash = [0 for i in range(0,128)] max = 0 for end in range(len(s)): #ord函数 - 字符转化为整数值 hash[ord(s[end])] += 1 flag = 0 for value in range(end-max,end): if hash[ord(s[value])] > 1: flag = 1 break if flag == 0: max += 1 elif flag == 1: hash[ord(s[end-max])] -= 1 return max |
C++版本：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Solution { public: int lengthOfLongestSubstring(string s) { int map[128] = {0}; int max = 0; for(int end = 0; end < s.length(); end++) { map[s[end]] += 1; int flag = 0; for(int i = end - max; i < end; i++) { if(map[s[i]] > 1) { flag = 1; break; } } if(flag == 0) { max += 1; } else { map[s[end - max]] -= 1; } } return max; } }; |
还是我C++熟…哈哈哈
更新动态规划，DP本质是根据前一状态(位置、下标)的最优解得出当前状态的最优解。
前一状态 和 当前状态 的区别就是： 新增了最后一个元素，它可能和前面的m个元素中的一个冲突，或完全不冲突(不可能同时和两个元素冲突)。
这里m值表示的是前一状态下的最优解max。
当前状态的max = 当前Index – 冲突Index;
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class Solution { public: int lengthOfLongestSubstring(string s) { int nSize = s.length(); if(nSize == 0) { return 0; } int nDPEnd = 1; int ans = 1; for(int end = 1; end < nSize; ++end) { int i = end - nDPEnd; while(i != end) { if(s[i] == s[end]) { nDPEnd = end - i; break; } i += 1; } if(i == end) { nDPEnd += 1; if(nDPEnd > ans) { ans = nDPEnd; } } } return ans; } }; |
这里nDPEnd在不同位置，标识的是不同状态下的max值。