44. Wildcard Matching

Understanding * Handling

This can be expressed as the transition formula d[i][j] = d[i-1][j] || d[i][j-1]. Its physical meaning is as follows:

1. Compare with "Above" (d[i-1][j]): Matches "zero" characters

Action: Ignore the current *.

Meaning: We assume this * does not exist at all (treat it as an empty string).

Logic: If the "pattern without this * (i-1)" can already match the "current string (j)", then adding this * will also definitely match, because * can represent nothing.

Visual Correlation: In the table, this means the result drops down from above. This explains why * can shorten the pattern but still hold true.

2. Compare with "Left" (d[i][j-1]): Matches "at least one" new character

Action: Let the * consume one more character from the string.

Meaning: We assume this * is already matching something, now let it "extend one more step".

Logic: If the "current pattern (including *)" can already match the "previous position of the string (j-1)", then because * can represent a sequence of arbitrary length, it only needs to "consume" the currently seen s[j-1] to successfully match up to the current position j.

explains why * can continuously extend the True state horizontally.