3 最长无重复

在一个字符串重寻找没有重复字母的最长子串。

  1. Input: "abcabcbb"
  2. Output: 3 
  3. Explanation: The answer is "abc", with the length of 3.

思路：
滑动窗口，维护一个能保持无重复字母的窗口

5 最长回文子串

  1. 输入：s = "babad"
  2. 输出："bab"
  3. 解释："aba" 同样是符合题意的答案。

思路：
动态规划：
dp[i][j] 表示s[i] - s[j] 是否为回文子串
dp[i][j] = s[i] == s[j] && dp[i-1][j-1] j - i > 1
扩展中心法
以某个字母为中心，左右两边扩展，得到此中心的最大回文子串
遍历中心，得到最大的回文子串

72 编辑距离

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
    1. 输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
    思路：dp[i][j] 表示以s1[i], s2[j] end的最小编辑距离.
    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1