LeetCode 003 的一点思考

Qustion:

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.

Coding:

拿到题目我的第一个思路是这是一个可以通过遍历完成的题，因为所有的情况之和明显是O(N^2)的时间复杂度。因此我的第一个方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int arr[256];
memset(arr, -1, 256*sizeof(int));
for(i=0; i<len; i++) {
	 for(j=i; j<len; j++) {
	 	if (arr[s[j]-'\0'] != -1) {
	 		i = arr[s[j]-'\0'];
	 		if(llen > maxllen)
	 			maxllen = llen;
	 		llen = 0;
	 		memset(arr, -1, 256*sizeof(int));
	 		break;         //1
	 	} else {
	 		llen++;
	 		arr[s[j]-'\0'] = j;
	 	}
	 }		
	 if(j == len) {
	 	if(llen > maxllen)
	 		maxllen = llen;
	 	break;            //2
	}
}

其中为了略微提高一下效率，使用了两个break。第一个是当在以i起始，j结尾的字符串中找到相同的两个字符时，另i直接定位到两个相同字符的前一个字符的后一位上，然后break。这是因为一定不会再出现包含这两个相同字符的子串满足要求，所以可以直接将i的位置后移。第二个是在一轮j的循环结束时，这时如果一直没有碰到过重复出现的字符，则表示从当前的i到结尾的整个子串上都没有重复的字符，所以当前的maxllen已经是全局最优的，这时也可以直接break结束。

结果在我提交上去这个版本的代码之后，卡在了这题的最后一个测试点上，显示的原因是运行超时。很显然，这样的遍历方法不是题目所期望的。所以就有了下面的一种方法，用动态规划来解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if(!len)
	 return 0;
dp[0] = 1;
for (i=1; i<len; i++) {
	for (j=i-1; j>=last_start; j--) {
	 	if(s[j] == s[i]) {  //1
	 		dp[i] = i - j;
	 		last_start = j + 1;
	 		break;
	 	} else if(j == last_start) {  //2
	 		dp[i] = dp[i-1] + 1;
	 	}
	 }
	 if(dp[i] > maxllen) {
	 	maxllen = dp[i];
	 }
}

这里的思路其实和我上面的解法思路有一点类似：对于任意一个位置点i，我们将它能与之前的点构成的最大子串的长度记作dp[i]（其中dp[0]=1）。对于每个位置来说，我们往前遍历，如果和该位置字符相同的字符的位置在上一轮相同位置字符的后面，则更新当前位置的 dp[i] = i-j ，并更新上一轮相同位置字符的位置到当前相同字符中前一个字符的位置后面；否则，说明当前位置的字符到上一轮相同位置字符之间没有相同的字符，则 dp[i] = dp[i-1] + 1 。由于这种方法在每次循环中均不需要完全遍历，所以效率相对较高。

但是上一个算法的时间复杂度仍然是O(N^2)数量级的，其实还可以存在一种时间复杂度只有O(N)的算法，就是用hash表来记录每个位置之前是否出现过某个字符，并且记录该字符坐标。这样可以不需要在for循环中进行遍历，可以直接从hash表中取得结果，速度快了不少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if(!len)
	return 0;
dp[0] = 1;
int hash[256];
memset(hash, -1, sizeof(int)*256);
hash[s[0]-'\0'] = 0;
for (i=1; i<len; i++) {
	ind = s[i]-'\0';
	if(hash[ind] != -1 && hash[ind] >= last_same) {
		dp[i] = i - hash[ind];
		last_same = hash[ind] + 1;
		hash[ind] = i;
	} else {
		dp[i] = dp[i-1] + 1;
		hash[ind] = i;
	}
	if(dp[i] > maxllen) {
		maxllen = dp[i];
		if(maxllen == 127)
			k = i;
	}
}

其中hash表中存每一个字符是否在之前出现过，如果出现过，记录它的位置坐标，如果没有，则为-1。因此每次可以很快地判断出当前字符在之前是否曾出现。

但当时把这个版本提交上去的时候发现所有测试点都顺利通过，除了最后一个：
如图所示，输出结果应该是95的可是变成了127。调试了半天以后发现原来是错把hash定义为char类型了。
如上图所示，这个时候如果在里面存储如128之类的数字，机器会自动理解成-128(因为是1字节，10000000)，所以导致了错误。因此这个hash的类型必须是int类型。

完整代码可参见我的Github: l_substring_without_rep.c

Reference: