FunctionRacerProblemsRace

Patterns With Repeat Marks

HardDynamic programmingPython, JavaScript, TypeScript, Java, C++

pattern is made of lowercase letters and the symbols ., * and +. A letter matches that same letter, and . matches any one letter. A * written right after a letter or . lets that item appear zero or more times in a row; a + lets it appear one or more times.

Return true if pattern matches the whole of text, from its first letter to its last, and false otherwise. A * or + always follows a letter or .: never another * or +, and never the start of the pattern. Both strings may be empty.

Example 1

text "mississippi"
pattern "mis+i.*p+."
returns true

mis+i covers missi, .* covers ssi, p+ covers pp and the final . covers i.

Example 2

text "aab"
pattern "c*a+b+."
returns false

c* can vanish and a+b+ covers aab, but the final . still needs one more letter.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems