首页 > 数据结构 > Hash表 > LeetCode-最长无重复字串[题解]
2014
03-21

LeetCode-最长无重复字串[题解]

Longest Substring Without Repeating Characters

题目难度:3   面试频率 2  . (1-5)

题目描述:

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.

链接:http://oj.leetcode.com/problems/longest-substring-without-repeating-characters/

大意:所有找出所有无重复字符的子串的最大长度。

基本思路是使用哈希,和大部分字符统计或字符重复的思路一样。再使用两个指针 ,一个指针为start 指向当前遍历的字串的开始位置,如果遇到重复字符x,就将 start的位置 改为上一个x 位置+1.

例如:对于 “abcdbef” 初始 start=0, 当遍历到 第二个 b时,检测到重复。上一个b的位置是1. 因此 start=b+1。 然后还有更新 hash。

//============================================================================
// Name        : Longest.cpp
// Author      : coder
// Version     :
// Copyright   : www.acmerblog.com
// Description : Longest Substring Without Repeating Characters
//============================================================================

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    	int hash[256];
    	for(int i=0; i<256; i++) hash[i] = -1;
    	int start = 0, ans = 0;
    	int i;
    	for(i=0; i<s.size(); i++){
    		if( -1 != hash[ s[i] ] ){
    			if(ans < i-start) ans = i-start;
    			for(int j=start; j<hash[ s[i] ]; j++) hash[j] = -1;
    			if(hash[  s[i] ] + 1  > start )
    				start = hash[ s[i] ] +1;
    		}
    		hash[ s[i]] = i;
    	}
    	if(ans < i-start) ans = i-start;
    	return ans;
    }
};

int main() {
	string str = "wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco";
	str = "abcdbef";
	Solution s ;
	cout << s.lengthOfLongestSubstring(str) << endl;
	return 0;
}

  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。