Здравствуйте!

Задачка — https://leetcode.com/problems/regular-expression-matching/

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

'.' Matches any single character.​​​​
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Накидал решение, оно мне выдаёт:

Input: "aab" "c*a*b"
Output: false
Expected: true

Я чего-то не так понял? Ведь не подходит же под маску, сразу на первом символе

Если баг, то куда там писать, чтобы починили?

Здравствуйте, Marty, Вы писали:

M>Здравствуйте!

M>Задачка — https://leetcode.com/problems/regular-expression-matching/

M>

M>Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

M>'.' Matches any single character.​​​​
M>'*' Matches zero or more of the preceding element.
M>The matching should cover the entire input string (not partial).

M>Накидал решение, оно мне выдаёт:
M>

M>Input: "aab" "c*a*b"
M>Output: false
M>Expected: true

M>Я чего-то не так понял? Ведь не подходит же под маску, сразу на первом символе

Подходит если звездочки раскрыть так:
"aab" -> "c{0}a{2}b"

Здравствуйте, vopl, Вы писали:


M>>Я чего-то не так понял? Ведь не подходит же под маску, сразу на первом символе

V>Подходит если звездочки раскрыть так:
V>"aab" -> "c{0}a{2}b"


Как я понял из условия, точка и звёздочка — они не относятся к предыдущему символу, а метасимволы сами по себе, типа как '?' и '*' в маске файла в винде

ЗЫ не внимательно читал — '*' Matches zero or more of the preceding element.

Так что да, ты прав

Здравствуйте, Marty, Вы писали:

M>Я чего-то не так понял? Ведь не подходит же под маску, сразу на первом символе

'*' Matches zero or more of the [b]preceding element.

У тебя первая звездочка сопоставляется с нулевым количеством букв "c", вторая — с двумя "a", и потом "b" сопоставляется с "b". Правильный ответ — true, твой алкогоритм говорит false.

P.S. Интересно, простая и наивная рекурсивная реализация их устроит, или на больших примерах будет работать слишком медленно, и они чего-то более хитрого хотят? Полноценное построение конечного автомата, я полагаю, большинство участников не потянет, но наверное можно придумать какой-то промежуточный по сложности алкогоритм, отталкиваясь от алгоритма Морриса-Пратта.

Здравствуйте, Pzz, Вы писали:

M>>Я чего-то не так понял? Ведь не подходит же под маску, сразу на первом символе

Pzz>

'*' Matches zero or more of the [b]preceding element.

Pzz>У тебя первая звездочка сопоставляется с нулевым количеством букв "c", вторая — с двумя "a", и потом "b" сопоставляется с "b". Правильный ответ — true, твой алкогоритм говорит false.

Да, я уже понял, что не правильно условие распарсил.


Pzz>P.S. Интересно, простая и наивная рекурсивная реализация их устроит, или на больших примерах будет работать слишком медленно, и они чего-то более хитрого хотят? Полноценное построение конечного автомата, я полагаю, большинство участников не потянет, но наверное можно придумать какой-то промежуточный по сложности алкогоритм, отталкиваясь от алгоритма Морриса-Пратта.

Да, я с рекурсией написал, и — "Ваше решение быстрее овер 60% других, и занимает меньше памяти, чем 30% других решений"