首页 > 代码库 > 【leetcode】 Longest Substring Without Repeating Characters
【leetcode】 Longest Substring Without Repeating Characters
题目:
给定一个字符串,返回该串没有重复字符的最长子串。
分析:
1)子串:子串要求是连续的。
2)无重复,出现重复就断了,必须从新的位置开始。而新的位置就是重复字符第一次出现位置的下一个位置。
3)整个串可能没有一处重复。
那么,为了找出当前访问的字符是否出现过,要怎么做呢?当然是hash,O(1)的时间,而且既然是字符, 定义个255的hash table 就可以了,hash table 中的元素为相应字符在s中出现的位置。初始化为-1,表示都没有出现。
我们另外定义一个start 和end变量,来记录当前不重复子串的起始点,再定义一个记录最长子串的max_len变量,当当前不重复子串的长度大于最大值时,更改其值。
看个例子:
初始时 start = end = 0,随着end的移动,将遇到的字符的index加入到hash table 中,直到end = 3 的时候,发现 hash[ s[ end ] ] != -1,说明字符 b 在前面出现了,也就是说出现了重复,那么此时我们记录当前不重复的子串的长度 = end - start = 3 , 也就是abc子串。将该值3与max_len进行比较,更新max_len 的值。
那么此时start 的值应该怎么更新是最终要的,图中我们将其更改为2,这是怎么得来的呢?因为子串要求是连续的,当end = 3出现重复时,说明从 0 开始的s最长无重复子串的长度就是 3,因为不允许跳过这个重复的b继续向后进行,所以,更长的子串肯定只能出现在第一个b字符的后一个字符为起始点的情况。
hash table的处理是将新 start前的元素清除,即改为 -1 ,同时保存从新start 到end间的信息。这样end 走到最后就完成了。
实现:
int lengthOfLongestSubstring(string s) { int len = s.size(); if(len <= 1) return len; //hash_table,record the index of items in s int hash_table[255]; //-1 means haven't occur memset(hash_table, -1, sizeof(hash_table)); int start = 0; int end = 0; int max_len = 0; while(end < len) { char c = s[end]; if(hash_table[c] == -1) hash_table[c] = end++; else { max_len = max(max_len, end - start); //new start start = hash_table[c] + 1; //clean items in hash_table . memset(hash_table, -1, sizeof(hash_table)); //record the index of items from new start to end. for(int i = start; i <= end; ++i) hash_table[s[i]] = i; ++end; } } //may be the s without repeating character from start to end. max_len = max(max_len, end - start); return max_len; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。