首页 > > 程序设计 > C/C++ >

Longest Substring Without Repeating Character…

2018-06-18 04:20:14来源：未知阅读 ()

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.com/problems/longest-substring-without-repeating-characters/

题目意思：给出一个字符串，输出最长的子串的长度，子串不能有重复的字符。（子串是连续的。）

解题思路：依次读取字符串的每一个字符，如果第一次出现则当前子串长度+1，否则：首先判断当前长度是否大于最大长度，是则替换最大长度。然后

　　　　　　查找重复的字符是在原字符串哪里出现的。

代码如下：

 1 int lengthOfLongestSubstring(char* s) {
 2     int maxlen = 0,currlen = 0;
 3     int table[128], i, j, start = 0;
 4     memset(table, 0, sizeof(table));
 5     for (i = 0; s[i] != '\0'; ++i){
 6         if( (++table[s[i]]) == 2 ){
 7             if (currlen > maxlen){
 8                 maxlen = currlen;
 9             }
10             for(j = start; j < i; ++j){ //start记录重复的字符后一个位置
11                 if (s[j] == s[i]){
12                     table[s[j]] = 1;
13                     start = j+1;
14                     break;
15                 }else{
16                     --currlen;
17                     table[s[j]] = 0;
18                 }
19             }
20         }else{
21             ++currlen;
22         }
23     }
24     if (currlen > maxlen){
25         maxlen = currlen;
26     }
27     return maxlen;
28 }