LeetCode 003 Longest Substring Without Repeating Characters 题解

题意

给一个字符串,求最长的不包含重复字符的连续子串的长度。例如字符串abcabcbb的最长连续子串是abc,其长度为3,返回3即可。

分析

第一反应是动态规划,想了一下发现不是。LeetCode给这个题的标签是“Hash Table”,我现在仍然不明白这道题跟哈希表与什么关系。是要用到一个数组才记录一些信息,但我觉得不是哈希表,所以我给这道题的归类为“其他类型”。

这道题的思路其实很简单,无非就是枚举所有子串,然后验证这些串里面是否有重复的字符。只不过“枚举”和“验证”两个过程都可以加一点特技。完全不加特技的方法是:枚举子串起点、枚举子串终点、扫描子串验证是否有重复字符。和在一起就是$O(n^3)$的时间复杂度,我没试,我猜会超时。

即使是最暴力的方法,在扫描验证的时候也需要一张表,来记录每个字符是否出现过,由于是8位char型,所以长度256的表就足够了,测试数据好像都是字母,不过还是开256的长度吧。其实这个表不光可以记录某个字母是否出现过,还可以记录它上次出现在什么位置。我们依次扫描输入字符串的每一个字符,同时记录下它们上一次出现的位置。扫描时,如果发现当前字符上次出现的位置在子串范围之内,就说明这个字符重复,如果在当前子串范围之外,则不重复。这样我们不需要重复扫描整个子串,就可以知道它其中是否有重复字符。这样我们就可以省掉“扫描验证”这个环节,将时间复杂度降到了$O(n^2)$。

同样,我们也可以省掉“枚举起点”这个过程,将起点初始化为0,然后在起点为0的子串后面追加字符,直到不能追加为止(再追加就会产生重复),然后通过某种时间复杂度为$O(1)$的手段,将起点直接移动到一个合适的位置,使得当前字符得以追加到子串当中。直到追加完整个字符串的最后一个字符为止。在整个过程中,子串的长度会变长也会变短,但始终都没有重复字符,我们记录下整个过程中最长的那个长度,就是问题的答案了。显然,这样优化之后问题的时间复杂度降为了$O(n)$。

说起来容易,那个传说中的时间复杂度为$O(1)$的“手段”是什么呢?其实很简单:我们用一个变量作为子串起点的游标,如果当前要追加的字符会导致重复,那我们就将重复点以及之前的所有字符全部舍弃,将记录起点的游标移动到与当前字符重复的那个字符的下一个字符。

需要注意的是,起点游标的移动方向必须是单向的,也就是起点游标必须一直向右,如果向左则不能保证子串中无重复字符。我在这里WA了一次,就是因为没限制起点游标的移动方向。没明白这句话什么意思的童鞋,可以试试abba这个测试数据,最长子串是ab或者ba,长度都是2。

另外还因为记录长度变量maxLen的初始化WA了一次,输入的字符串有可能为空串,空串的最长子串长度显然为0。

C代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lengthOfLongestSubstring(char *s) {
int len = strlen(s);
int pt = 0;
int maxLen = -1;
int st[256];
memset(st, -1, 256 * sizeof(int));
for(int i = 0; i < len; i++)
{
if(st[s[i]] != -1 && st[s[i]] >= pt)
{
pt = st[s[i]] + 1;
}
st[s[i]] = i;
if(maxLen < i - pt) maxLen = i - pt;
}
return maxLen + 1;
}

其中pt就是起点游标,st就是记录某个字符上次出现的位置的数组,st[s[i]] >= pt用于限制起点游标移动的方向,最后的maxLen值就是问题的答案。


版权声明

The Bloom of Youth by KUANG Qi is licensed under a Creative Commons BY-NC-ND 4.0 International License.
况琪创作并维护的锦瑟华年博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于The Bloom of Youth | 锦瑟华年博客( http://kuangqi.me ),版权所有,侵权必究。

本文永久链接:http://kuangqi.me/programming/leetcode-longest-substring-without-repeating-characters/