题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 数据范围:s.length≤40000
题解:动态规划
哈希表统计: 遍历字符串 s 时,使用哈希表(记为 dic )统计 各字符最后一次出现的索引位置 。 左边界 i
获取方式: 遍历到 s[j]时,可通过访问哈希表 dic[s[j]]获取最近的相同字符的索引 i。
复杂度分析: 时间复杂度 O(N) : 其中 N 为字符串长度,动态规划需遍历计算 dp 列表。
空间复杂度 O(1) :字符的 ASCII 码范围为 0 ~ 127 ,哈希表 dic 最多使用 O(128) = O(1) 大小的额外空间
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param s string字符串
* @return int整型
*/
int lengthOfLongestSubstring(string s) {
// write code here
vector<int> dp(128,-1); //字符的 ASCII 码范围为 0 ~ 127
int maxlen=0; //最大长度结果
int begin = -1; //起始值设置位-1,字符的 ASCII 码范围为 0 ~ 127
for(int i =0;i<s.size();i++){
if(dp[s[i]]>begin) //存在
begin = dp[s[i]];
dp[s[i]] = i;
maxlen = max(maxlen,i-begin);
}
return maxlen;
}
};