【笔记】LeetCode字符串匹配_leetcode 字符串匹配

最长不含重复字符的子字符串

https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
解题思路：

1. 哈希表board + 双指针 (i, j)，哈希表保存字符上次出现位置，i 保存没有重复字符的首地址
2. 动态规划：dp[i] 表示当前位置上最长的字符串，当不重复 dp[i] = dp[i-1] + 1，当出现重复则先更新 i 的位置 dp[i] = j - i

具体：

1. 遍历字符串，保存路径上的每个字符的位置到哈希表 board 中
2. 当没有重复字符出现时，ans++。当出现重复字符的时候，应该重新定位 i 的位置

优化：

1. 我们只需要所有子串中最长的长度，而且每次长度都只与 j - i 有关

class Solution {
   
public:
    int lengthOfLongestSubstring(string s) 
    {
   
        // 用一个map保存字符上次出现的位置
        // 遍历字符串
        // 如果字符没有出现过，则cur++
        // 如果字符出现过，则更新 i 的下标为 max(i, board[s[i]])，原因：上次重复的位置可能在i前面，但 i 只能表示当前没有重复的位置
        unordered_map<char, int> board;
        int i = 0, j = 0, ans = 0, cur = 0;
        for (int j = 0; j < s.size(); ++j)
        {
   
            if (board.count(s[j]))
            {
   
                // 字符s[j]出现过
                i = max(board[s[j]], i);
                cur = j - i;            
            }
            else 
                ++cur;
            ans = max(cur, ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24