> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0010_regular_expression_matching/slt.md).

# slt

#### Solutuion 1 递归

注意`*`一定是match preceding char，`*`不会出现在第一个位置

#### Solutuion 2 DP

```
dp[i][j]: if s[0..i-1] matches p[0..j-1]

if p[j-1] != '*':
    dp[i][j] = dp[i-1][j-1] && s[i-1] == p[j-1]

if p[j-1] == '*': (denote p[j-2] with x)
    dp[i][j] is true iff any of the following is true
    1) "x*" repeats 0 time and matches empty: dp[i][j-2]
    2) "x*" repeats >= 1 times and matches "x*x": s[i-1] == x && dp[i-1][j]
```