Appearance
高频字符串
最长无重复子串
题意：给你一个字符串，找出“不包含重复字符的最长连续子串”的长度。注意是子串，必须连续，不是子序列。
核心用滑动窗口 + 哈希表：
右指针 right 一直往右扫描。 左指针 left 表示当前无重复窗口的左边界。 哈希表 lastIndex 记录每个字符上一次出现的位置。 如果当前字符在窗口里重复了，就把 left 跳到它上一次出现位置的后一位。
c
using System.Collections.Generic; // 引入 Dictionary 字典集合
public class Solution // 定义题解类
{ // 类开始
public int LengthOfLongestSubstring(string s) // 定义方法，返回最长无重复子串长度
{ // 方法开始
if (string.IsNullOrEmpty(s)) // 如果字符串为空或者长度为 0
{ // 条件开始
return 0; // 没有子串，直接返回 0
} // 条件结束
Dictionary<char, int> lastIndex = new Dictionary<char, int>(); // 记录每个字符最后一次出现的位置
int left = 0; // 滑动窗口左边界
int maxLength = 0; // 当前找到的最长无重复子串长度
for (int right = 0; right < s.Length; right++) // 右指针从左到右遍历字符串
{ // 循环开始
char current = s[right]; // 取出当前右指针指向的字符
if (lastIndex.ContainsKey(current) && lastIndex[current] >= left) // 如果当前字符出现过，并且上次位置还在窗口内
{ // 条件开始
left = lastIndex[current] + 1; // 左边界跳到重复字符上一次出现位置的后一位
} // 条件结束
lastIndex[current] = right; // 更新当前字符最后一次出现的位置
int currentLength = right - left + 1; // 计算当前窗口长度
if (currentLength > maxLength) // 如果当前窗口更长
{ // 条件开始
maxLength = currentLength; // 更新最长长度
} // 条件结束
} // 循环结束
return maxLength; // 返回最终答案
} // 方法结束
} // 类结束复杂度
时间复杂度：O(n)，每个字符最多被右指针扫描一次。 空间复杂度：O(字符集大小)，哈希表存字符最近位置。
面试记忆
NOTE
右指针扩张窗口，哈希表查重复；重复字符还在窗口内时，左指针跳到它上次出现位置的后一位。
最长回文子串
最长回文子串
题意：在字符串里找出最长的回文子串。回文就是正着读、反着读都一样，比如 "aba"、"bb"、"racecar"。
核心思路
回文有一个特点：它一定是围绕中心对称的。 所以我们枚举每个位置作为中心，然后向左右两边扩展。
要注意两种中心：
aba 这种是奇数长度，中心是一个字符。 abba 这种是偶数长度，中心是两个字符中间。
c
public class Solution // 定义题解类
{ // 类开始
public string LongestPalindrome(string s) // 定义方法，返回最长回文子串
{ // 方法开始
if (string.IsNullOrEmpty(s)) // 如果字符串为空或者为 null
{ // 条件开始
return ""; // 没有回文子串，返回空字符串
} // 条件结束
int start = 0; // 记录最长回文子串的起始位置
int maxLength = 1; // 记录最长回文子串的长度，单个字符本身就是回文
for (int center = 0; center < s.Length; center++) // 枚举每一个位置作为中心
{ // 循环开始
int oddLength = ExpandAroundCenter(s, center, center); // 计算奇数长度回文，比如 aba
int evenLength = ExpandAroundCenter(s, center, center + 1); // 计算偶数长度回文，比如 abba
int currentLength = oddLength > evenLength ? oddLength : evenLength; // 取两种情况中更长的长度
if (currentLength > maxLength) // 如果当前回文比之前记录的更长
{ // 条件开始
maxLength = currentLength; // 更新最长长度
start = center - (currentLength - 1) / 2; // 根据中心和长度反推出起始位置
} // 条件结束
} // 循环结束
return s.Substring(start, maxLength); // 截取并返回最长回文子串
} // 方法结束
private int ExpandAroundCenter(string s, int left, int right) // 从给定左右位置开始向外扩展
{ // 方法开始
while (left >= 0 && right < s.Length && s[left] == s[right]) // 只要不越界且左右字符相等，就继续扩展
{ // 循环开始
left--; // 左指针向左移动
right++; // 右指针向右移动
} // 循环结束
return right - left - 1; // 返回扩展结束后的回文长度
} // 方法结束
} // 类结束复杂度
时间复杂度：O(n²)，每个中心最坏都可能向两边扩展。 空间复杂度：O(1)，只用了几个变量。
面试记忆
CAUTION
每个位置都当中心；奇数扩一次，偶数扩一次；谁更长就更新答案。
字符串相加
题意：两个很大的非负整数用字符串表示，不能直接转成 int / long，要像小学竖式加法一样算出结果。
核心：从右往左加，维护 carry 进位。当前位结果是 sum % 10，新的进位是 sum / 10。
c
using System.Text; // 引入 StringBuilder，用来高效拼接字符串
public class Solution // 定义题解类
{ // 类开始
public string AddStrings(string num1, string num2) // 定义字符串相加方法
{ // 方法开始
int i = num1.Length - 1; // 指向 num1 的最后一位，也就是个位
int j = num2.Length - 1; // 指向 num2 的最后一位，也就是个位
int carry = 0; // 记录进位，初始没有进位
StringBuilder builder = new StringBuilder(); // 保存从低位到高位算出来的结果
while (i >= 0 || j >= 0 || carry > 0) // 只要还有数字没算完，或者还有进位，就继续
{ // 循环开始
int digit1 = i >= 0 ? num1[i] - '0' : 0; // 如果 num1 还有数字，就转成数字，否则当作 0
int digit2 = j >= 0 ? num2[j] - '0' : 0; // 如果 num2 还有数字，就转成数字，否则当作 0
int sum = digit1 + digit2 + carry; // 当前位相加，并加上上一轮的进位
int digit = sum % 10; // 当前位真正留下来的数字
carry = sum / 10; // 当前位产生的新进位
builder.Append((char)(digit + '0')); // 把当前位结果转回字符，并追加到结果里
i--; // num1 指针向左移动一位
j--; // num2 指针向左移动一位
} // 循环结束
char[] chars = builder.ToString().ToCharArray(); // 把低位到高位的结果转成字符数组
System.Array.Reverse(chars); // 因为我们是从个位开始追加的，所以最后需要反转
return new string(chars); // 把反转后的字符数组转成字符串并返回
} // 方法结束
} // 类结束复杂度
时间复杂度：O(max(m, n))。 空间复杂度：O(max(m, n))，主要是返回结果需要空间。
面试记忆
WARNING
从右往左加，短的补 0，每位算 sum % 10，进位算 sum / 10，最后反转结果。
字符串乘法
字符串乘法
题意：两个很大的非负整数用字符串表示，不能直接转成 int / long，要返回它们相乘后的字符串。
核心：模拟竖式乘法。num1[i] 和 num2[j] 相乘后，结果主要落在 i + j + 1 位置，进位落在 i + j 位置。
c
using System.Text; // 引入 StringBuilder，用来高效拼接最终字符串
public class Solution // 定义题解类
{ // 类开始
public string Multiply(string num1, string num2) // 定义字符串乘法方法
{ // 方法开始
if (num1 == "0" || num2 == "0") // 如果任意一个数是 0
{ // 条件开始
return "0"; // 乘积一定是 0
} // 条件结束
int m = num1.Length; // 记录 num1 的长度
int n = num2.Length; // 记录 num2 的长度
int[] result = new int[m + n]; // 两个数相乘，结果最多有 m + n 位
for (int i = m - 1; i >= 0; i--) // 从 num1 的个位开始往左遍历
{ // 外层循环开始
int digit1 = num1[i] - '0'; // 把 num1 当前字符转成数字
for (int j = n - 1; j >= 0; j--) // 从 num2 的个位开始往左遍历
{ // 内层循环开始
int digit2 = num2[j] - '0'; // 把 num2 当前字符转成数字
int product = digit1 * digit2; // 计算当前两位数字的乘积
int p1 = i + j; // 进位应该累加到的位置
int p2 = i + j + 1; // 当前位结果应该落到的位置
int sum = product + result[p2]; // 当前乘积加上这个位置之前累积的值
result[p2] = sum % 10; // 当前位只保留个位数字
result[p1] += sum / 10; // 十位部分作为进位累加到前一位
} // 内层循环结束
} // 外层循环结束
StringBuilder builder = new StringBuilder(); // 创建字符串构建器
int index = 0; // 从结果数组开头开始扫描
while (index < result.Length && result[index] == 0) // 跳过前导 0
{ // 循环开始
index++; // 移动到下一位
} // 循环结束
while (index < result.Length) // 把剩余数字拼成字符串
{ // 循环开始
builder.Append(result[index]); // 追加当前数字
index++; // 移动到下一位
} // 循环结束
return builder.Length == 0 ? "0" : builder.ToString(); // 返回最终乘积字符串
} // 方法结束
} // 类结束复杂度
时间复杂度：O(m * n)，两个字符串每一位都要相乘。 空间复杂度：O(m + n)，结果数组最多需要 m + n 位。
面试记忆
IMPORTANT
两位相乘落在 i + j + 1，进位加到 i + j；最后跳过前导 0 拼成字符串。
KMP 字符串匹配
KMP 用来在 haystack 里找 needle 第一次出现的位置。它的核心优势是：匹配失败时，主串指针 i 不回退，只让模式串指针 j 根据 lps 表跳转。
lps 表表示：当前这段模式串里，最长相同真前缀和真后缀的长度。 比如 pattern = "ababaca"，它的 lps = [0,0,1,2,3,0,1]。
c
public class Solution // 定义题解类
{ // 类开始
public int StrStr(string haystack, string needle) // 在 haystack 中查找 needle 第一次出现的位置
{ // 方法开始
if (needle.Length == 0) // 如果模式串为空
{ // 条件开始
return 0; // 空串默认从下标 0 开始匹配
} // 条件结束
int[] lps = BuildLps(needle); // 构建 needle 的 lps 表
int i = 0; // i 指向主串 haystack
int j = 0; // j 指向模式串 needle
while (i < haystack.Length) // 只要主串还没有扫描完
{ // 循环开始
if (haystack[i] == needle[j]) // 如果当前两个字符匹配
{ // 条件开始
i++; // 主串指针向后移动
j++; // 模式串指针向后移动
if (j == needle.Length) // 如果模式串已经全部匹配完成
{ // 条件开始
return i - j; // 返回匹配起点
} // 条件结束
} // 条件结束
else // 如果当前两个字符不匹配
{ // 分支开始
if (j > 0) // 如果模式串已经匹配过一部分
{ // 条件开始
j = lps[j - 1]; // 模式串指针跳到可复用前缀的位置
} // 条件结束
else // 如果 j 已经在模式串开头
{ // 分支开始
i++; // 主串指针只能向后移动
} // 分支结束
} // 分支结束
} // 循环结束
return -1; // 扫描结束仍然没有找到，返回 -1
} // 方法结束
private int[] BuildLps(string pattern) // 构建模式串的 lps 表
{ // 方法开始
int[] lps = new int[pattern.Length]; // 创建 lps 数组
int len = 0; // len 表示当前最长相同前后缀长度
int i = 1; // 从下标 1 开始计算，因为 lps[0] 一定是 0
while (i < pattern.Length) // 遍历整个模式串
{ // 循环开始
if (pattern[i] == pattern[len]) // 如果当前字符能延长前后缀匹配
{ // 条件开始
len++; // 最长相同前后缀长度加 1
lps[i] = len; // 记录当前位置的 lps 值
i++; // 继续处理下一个字符
} // 条件结束
else // 如果当前字符不能匹配
{ // 分支开始
if (len > 0) // 如果之前还有可回退的前后缀长度
{ // 条件开始
len = lps[len - 1]; // len 回退到更短的可复用前缀
} // 条件结束
else // 如果 len 已经是 0
{ // 分支开始
lps[i] = 0; // 当前没有相同前后缀
i++; // 继续处理下一个字符
} // 分支结束
} // 分支结束
} // 循环结束
return lps; // 返回构建好的 lps 表
} // 方法结束
} // 类结束复杂度
时间复杂度：O(n + m)，n 是主串长度，m 是模式串长度。 空间复杂度：O(m)，主要是 lps 表。
面试记忆
TIP
匹配成功：i、j 一起走。 匹配失败：i 不动，j = lps[j - 1]。
最小覆盖子串
题意：给你两个字符串 s 和 t，在 s 里找一个最短的连续子串，让它包含 t 里的所有字符和次数。
核心是滑动窗口：
right 负责扩大窗口，直到窗口覆盖 t。 left 负责缩小窗口，在仍然覆盖 t 的情况下尽量变短。 need 记录 t 里需要哪些字符。 window 记录当前窗口里有哪些字符。 valid 表示当前有多少种字符已经满足需求。
c
using System.Collections.Generic; // 引入 Dictionary 字典集合
public class Solution // 定义题解类
{ // 类开始
public string MinWindow(string s, string t) // 定义最小覆盖子串方法
{ // 方法开始
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) // 如果 s 或 t 为空
{ // 条件开始
return ""; // 不可能找到覆盖子串，返回空字符串
} // 条件结束
Dictionary<char, int> need = new Dictionary<char, int>(); // 记录 t 中每个字符需要出现的次数
Dictionary<char, int> window = new Dictionary<char, int>(); // 记录当前窗口中每个字符出现的次数
foreach (char c in t) // 遍历 t 中的每个字符
{ // 循环开始
if (!need.ContainsKey(c)) // 如果 need 中还没有这个字符
{ // 条件开始
need[c] = 0; // 先把这个字符的需求次数初始化为 0
} // 条件结束
need[c]++; // 当前字符需求次数加 1
} // 循环结束
int left = 0; // 滑动窗口左边界
int right = 0; // 滑动窗口右边界
int valid = 0; // 已经满足需求的字符种类数量
int start = 0; // 最小覆盖子串的起始位置
int minLength = int.MaxValue; // 最小覆盖子串的长度，初始为最大值
while (right < s.Length) // 右指针没有走完整个字符串时继续
{ // 外层循环开始
char addChar = s[right]; // 取出即将加入窗口的字符
right++; // 右边界右移，扩大窗口
if (need.ContainsKey(addChar)) // 如果这个字符是 t 需要的字符
{ // 条件开始
if (!window.ContainsKey(addChar)) // 如果窗口表里还没有这个字符
{ // 条件开始
window[addChar] = 0; // 初始化窗口中该字符的次数
} // 条件结束
window[addChar]++; // 窗口中该字符次数加 1
if (window[addChar] == need[addChar]) // 如果这个字符的数量刚好满足需求
{ // 条件开始
valid++; // 满足需求的字符种类数量加 1
} // 条件结束
} // 条件结束
while (valid == need.Count) // 当窗口已经覆盖 t 时，尝试收缩左边界
{ // 内层循环开始
if (right - left < minLength) // 如果当前窗口比之前记录的更短
{ // 条件开始
start = left; // 更新最短窗口起点
minLength = right - left; // 更新最短窗口长度
} // 条件结束
char removeChar = s[left]; // 取出即将移出窗口的字符
left++; // 左边界右移，缩小窗口
if (need.ContainsKey(removeChar)) // 如果移出的字符是 t 需要的字符
{ // 条件开始
if (window[removeChar] == need[removeChar]) // 如果移出前这个字符刚好满足需求
{ // 条件开始
valid--; // 移出后会导致该字符不再满足需求
} // 条件结束
window[removeChar]--; // 窗口中该字符次数减 1
} // 条件结束
} // 内层循环结束
} // 外层循环结束
return minLength == int.MaxValue ? "" : s.Substring(start, minLength); // 如果没找到返回空，否则返回最短子串
} // 方法结束
} // 类结束复杂度
时间复杂度：O(n + m)，n 是 s 长度，m 是 t 长度。 空间复杂度：O(字符集大小)，主要是 need 和 window 两张表。
面试记忆
CAUTION
right 让窗口满足条件，left 在满足条件时尽量缩短窗口。
字母异位词分组
题意：把由相同字母组成的字符串分到一组，比如 "eat"、"tea"、"ate" 都属于一组。
核心：给每个字符串生成一个统一的 key。最简单的 key 是“排序后的字符串”。 比如：
eat -> aettea -> aetate -> aet
它们 key 一样，所以放进同一个组。
c
using System; // 引入 Array.Sort，用来排序字符数组
using System.Collections.Generic; // 引入 Dictionary、List、IList 集合类型
public class Solution // 定义题解类
{ // 类开始
public IList<IList<string>> GroupAnagrams(string[] strs) // 定义字母异位词分组方法
{ // 方法开始
Dictionary<string, List<string>> map = new Dictionary<string, List<string>>(); // 创建字典，key 是排序后的字符串，value 是同组单词列表
foreach (string word in strs) // 遍历每一个字符串
{ // 循环开始
char[] chars = word.ToCharArray(); // 把当前字符串转成字符数组
Array.Sort(chars); // 对字符数组排序，得到统一顺序
string key = new string(chars); // 把排序后的字符数组转回字符串，作为分组 key
if (!map.ContainsKey(key)) // 如果字典里还没有这个 key
{ // 条件开始
map[key] = new List<string>(); // 创建一个新的分组列表
} // 条件结束
map[key].Add(word); // 把当前单词加入对应分组
} // 循环结束
List<IList<string>> result = new List<IList<string>>(); // 创建最终返回结果
foreach (List<string> group in map.Values) // 遍历字典里的每一个分组
{ // 循环开始
result.Add(group); // 把当前分组加入结果
} // 循环结束
return result; // 返回所有分组
} // 方法结束
} // 类结束复杂度
假设有 n 个字符串，每个字符串平均长度是 k。 时间复杂度：O(n * k log k)，因为每个字符串都要排序。 空间复杂度：O(n * k)，结果和字典都要保存字符串。
面试记忆
WARNING
异位词只是字母顺序不同；把每个字符串排序成同一个 key，相同 key 放进同一个 List。
反转单词
题意：把字符串里的单词顺序反过来，同时去掉首尾空格，并把多个空格压成一个空格。
比如：
" the sky is blue " 变成：
"blue is sky the"
核心：从右往左扫描。因为最后一个单词应该最先输出。
c
using System.Text; // 引入 StringBuilder，用来高效拼接结果字符串
public class Solution // 定义题解类
{ // 类开始
public string ReverseWords(string s) // 定义反转单词方法
{ // 方法开始
StringBuilder builder = new StringBuilder(); // 创建结果构建器
int i = s.Length - 1; // 从字符串最后一个字符开始扫描
while (i >= 0) // 只要还没有扫描到字符串开头
{ // 外层循环开始
while (i >= 0 && s[i] == ' ') // 跳过右侧或单词之间的连续空格
{ // 跳空格循环开始
i--; // 指针向左移动
} // 跳空格循环结束
if (i < 0) // 如果跳过空格后已经越界
{ // 条件开始
break; // 说明没有单词了，退出循环
} // 条件结束
int end = i; // 记录当前单词的结束位置
while (i >= 0 && s[i] != ' ') // 向左找到当前单词的开头
{ // 找单词循环开始
i--; // 指针向左移动
} // 找单词循环结束
int start = i + 1; // 当前单词的起始位置
int length = end - start + 1; // 当前单词的长度
if (builder.Length > 0) // 如果结果里已经有单词
{ // 条件开始
builder.Append(' '); // 在新单词前补一个空格
} // 条件结束
builder.Append(s.Substring(start, length)); // 把当前单词追加到结果中
} // 外层循环结束
return builder.ToString(); // 返回反转后的字符串
} // 方法结束
} // 类结束复杂度
时间复杂度：O(n)，每个字符最多被扫描一次。 空间复杂度：O(n)，结果字符串需要空间。
面试记忆
IMPORTANT
从右往左找单词；跳过空格，截出单词；结果非空时先补一个空格再追加。
实现 strStr
题意：在 haystack 中查找 needle 第一次出现的位置，找到返回下标，找不到返回 -1。如果 needle 是空字符串，返回 0。
面试里简单写法是暴力匹配，复杂度 O(n * m)。更漂亮的写法是 KMP，复杂度 O(n + m)。
c
public class Solution // 定义题解类
{ // 类开始
public int StrStr(string haystack, string needle) // 在 haystack 中查找 needle 第一次出现的位置
{ // 方法开始
if (needle.Length == 0) // 如果 needle 是空字符串
{ // 条件开始
return 0; // 按题意返回 0
} // 条件结束
if (needle.Length > haystack.Length) // 如果 needle 比 haystack 还长
{ // 条件开始
return -1; // 一定不可能匹配成功
} // 条件结束
int[] lps = BuildLps(needle); // 构建 needle 的 lps 表
int i = 0; // i 指向 haystack 当前比较位置
int j = 0; // j 指向 needle 当前比较位置
while (i < haystack.Length) // 只要 haystack 还没有扫描完
{ // 循环开始
if (haystack[i] == needle[j]) // 如果当前两个字符相等
{ // 条件开始
i++; // haystack 指针向后移动
j++; // needle 指针向后移动
if (j == needle.Length) // 如果 needle 已经全部匹配完成
{ // 条件开始
return i - j; // 返回匹配起始下标
} // 条件结束
} // 条件结束
else // 如果当前两个字符不相等
{ // 分支开始
if (j > 0) // 如果 needle 已经匹配过一部分
{ // 条件开始
j = lps[j - 1]; // needle 指针回退到可复用前缀位置
} // 条件结束
else // 如果 needle 还在开头
{ // 分支开始
i++; // haystack 指针向后移动
} // 分支结束
} // 分支结束
} // 循环结束
return -1; // 扫描完还没找到，返回 -1
} // 方法结束
private int[] BuildLps(string pattern) // 构建 KMP 的 lps 表
{ // 方法开始
int[] lps = new int[pattern.Length]; // 创建 lps 数组
int len = 0; // len 表示当前最长相同前后缀长度
int i = 1; // 从下标 1 开始计算，因为 lps[0] 一定是 0
while (i < pattern.Length) // 遍历整个 pattern
{ // 循环开始
if (pattern[i] == pattern[len]) // 如果当前字符能延长前后缀
{ // 条件开始
len++; // 最长相同前后缀长度加 1
lps[i] = len; // 记录当前位置的 lps 值
i++; // 继续处理下一个字符
} // 条件结束
else // 如果当前字符不能延长前后缀
{ // 分支开始
if (len > 0) // 如果还有更短的前后缀可以尝试
{ // 条件开始
len = lps[len - 1]; // len 回退到更短的可复用前缀
} // 条件结束
else // 如果 len 已经是 0
{ // 分支开始
lps[i] = 0; // 当前下标没有相同前后缀
i++; // 继续处理下一个字符
} // 分支结束
} // 分支结束
} // 循环结束
return lps; // 返回构建好的 lps 表
} // 方法结束
} // 类结束复杂度
时间复杂度：O(n + m)。 空间复杂度：O(m)，m 是 needle 长度。
面试记忆
TIP
needle 为空返回 0；匹配完整返回 i - j；匹配失败时 i 不回退，j = lps[j - 1]。
正则表达式匹配
这里的正则只包含两个特殊符号：
.：匹配任意一个字符。 *：匹配它前面的字符出现 0 次或多次。 注意：这是完整匹配，不是看 s 里面是否包含某一段。
核心用 DP：
dp[i][j] 表示：s 的前 i 个字符，能不能匹配 p 的前 j 个字符。
普通字符或 .：
c
dp[i][j] = dp[i - 1][j - 1]遇到 * 有两种选择：
* 匹配 0 次：看 dp[i][j - 2]。 * 匹配 1 次或多次：如果前一个字符能匹配当前字符，看 dp[i - 1][j]。
c
public class Solution // 定义题解类
{ // 类开始
public bool IsMatch(string s, string p) // 判断字符串 s 是否能被模式串 p 完整匹配
{ // 方法开始
int m = s.Length; // 记录字符串 s 的长度
int n = p.Length; // 记录模式串 p 的长度
bool[,] dp = new bool[m + 1, n + 1]; // dp[i,j] 表示 s 前 i 个字符能否匹配 p 前 j 个字符
dp[0, 0] = true; // 空字符串可以匹配空模式串
for (int j = 2; j <= n; j++) // 初始化空字符串匹配模式串的情况
{ // 循环开始
if (p[j - 1] == '*') // 如果当前模式字符是 *
{ // 条件开始
dp[0, j] = dp[0, j - 2]; // * 可以让前一个字符出现 0 次，所以消掉前一个字符和 *
} // 条件结束
} // 循环结束
for (int i = 1; i <= m; i++) // 枚举 s 的前 i 个字符
{ // 外层循环开始
for (int j = 1; j <= n; j++) // 枚举 p 的前 j 个字符
{ // 内层循环开始
if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) // 如果当前字符能直接匹配
{ // 条件开始
dp[i, j] = dp[i - 1, j - 1]; // 当前字符匹配成功，结果取决于前面的部分是否匹配
} // 条件结束
else if (p[j - 1] == '*' && j >= 2) // 如果当前模式字符是 *，并且它前面有字符
{ // 分支开始
dp[i, j] = dp[i, j - 2]; // 情况一：* 匹配 0 次，直接删掉前一个字符和 *
char previous = p[j - 2]; // 取出 * 前面的那个字符
if (previous == '.' || previous == s[i - 1]) // 如果 * 前面的字符可以匹配 s 当前字符
{ // 条件开始
dp[i, j] = dp[i, j] || dp[i - 1, j]; // 情况二：* 匹配 1 次或多次，继续用当前模式匹配更短的 s
} // 条件结束
} // 分支结束
} // 内层循环结束
} // 外层循环结束
return dp[m, n]; // 返回整个 s 是否能被整个 p 完整匹配
} // 方法结束
} // 类结束复杂度
时间复杂度：O(m * n)。 空间复杂度：O(m * n)。
面试记忆
NOTE
普通字符看左上角；* 有两条路：匹配 0 次看左两格，匹配多次看上一行同列。