《剑指Offer》-48-最长不含重复字符串的子字符串

Yao's Blog / 2023-08-11 / 原文

这题以前做过，和力扣-3 重复

	int lengthOfLongestSubstring(string s) {
		// 本来应该是用map，但是其实可以使用数组替代，下标对应了字母
		unordered_map<char, int> map;
		int len = s.size(),maxLen=0;// 初始化为0是因为可能字符串长度为0
		vector<int> dp(len+1, 0);// 多一个，0不用
		for (int i = 0; i < len; i++) {
			if (map.count(s[i])) {
				// 字母出现重复
				dp[i + 1] = i - map[s[i]];
			}
			else dp[i + 1] = dp[i] + 1;

			map[s[i]] = i;//更新索引
			maxLen = max(maxLen, dp[i + 1]);
		}
		return maxLen;
	}

因为字符不只是小写字母，于是我将集合从数组改成了 map，但这仍然是错误的，关键是没有考虑到这种情况

"abba"

也就是当当前字符与重复字符之间的字符长度 > dp[i-1] 的时候，也就是说内部存在了重复段

为什么不需要考虑嵌套的情况？因为 dp 本身就是递归的，已经考虑过了

此时的dp[i]=dp[i-1]+1

	int lengthOfLongestSubstring(string s) {
		unordered_map<char, int> map;
		int len = s.size(), maxLen = 0;// 初始化为0是因为可能字符串长度为0
		vector<int> dp(len + 1, 0);// 多一个，0不用
		for (int i = 0; i < len; i++) {
			if (map.count(s[i])) {
				int distance = i - map[s[i]];
				// 如果距离 > 以上一个字符结尾的字符串中最长，说明包含了重复字符，+1
				// < 说明内部不包含重复字符
				// 相等是什么情况？比如 aa，此时应该是 1
				// 不需要考虑abccba，因为这种迭代根本就不会出现这种情况
				if (distance <= dp[i])dp[i + 1] = distance;
				else dp[i + 1] = dp[i] + 1;
			}
			else dp[i + 1] = dp[i] + 1;

			map[s[i]] = i;//更新索引
			maxLen = max(maxLen, dp[i + 1]);
		}
		return maxLen;
	}

第一次通过代码

优化

	int lengthOfLongestSubstring(string s) {
		unordered_map<char, int> map;
		int len = s.size(), maxLen = 0;// 初始化为0是因为可能字符串长度为0
		int pre = 0, prepre = 0;
		for (int i = 0; i < len; i++) {
			if (map.count(s[i]) && i - map[s[i]] <= prepre) pre = i - map[s[i]];
			else pre = prepre + 1;
			prepre = pre;

			map[s[i]] = i;//更新索引
			maxLen = max(maxLen, pre);
		}
		return maxLen;
	}

优化掉了一维数组以及优化了判断结构