String Matching Backtracking

Opening scenario

Regular Expression Matching (LC 10): implement isMatch(s, p) where p may contain . (any single char) and * (zero or more of the preceding element); the pattern must match the entire string. Follow-up you should expect: Word Break II (LC 140) — given a string s and a dictionary of words, return every sentence that splits s into those words.

LC numbers identify LeetCode problems.

For LC 10, assume a valid pattern: each * follows a literal or ., and is not itself repeated by another *. For Word Break II, words are nonempty and may be reused; every returned sentence must consume the entire input string. Compare the choices in a* with choosing the first dictionary word: what information determines the remaining problem?

Question progression

Q1 — Why is matching * a search, not a scan?

Question: Without *, matching is a simple character-by-character walk. What does * introduce that forces you to try alternatives?

Reasoning:…