Leetcode #10. Regular Expression Matching. Решение
FurryCatСсылка: https://leetcode.com/problems/regular-expression-matching/description/
Условия задачи: https://t.me/furrycat/503
Условия
Нужно реализовать простейшее регулярное выражение. На вход получаем строку s и паттерн p. Задача - проверить, соответствует ли строка паттерну.
- Проверяется полное совпадение строки - от начала и до конца.
- Строка содержит только английские буквы в нижнем регистре.
- Паттерн может содержать английские буквы в нижнем регистре, а также символы . и *.
При этом символ . (точка) означает один любой символ.
А символ * (звездочка) относится к предыдущему символу и означает нуль или больше. То есть паттерн "a*" соответствует строкам "a", "aa", "aaaaaa", а также пустой строке "".
В паттерне может быть комбинация ".*", которая означает нуль и более любых символов.
Решение
Это задача уровня hard, поэтому решение полностью взято из комментариев к задаче на leetcode.
Предлагается использовать динамическое программирование, то есть брать базовый случай и постепенно усложнять его, выводя новый этап решения из предыдущего.
Базовый случай
В нашей задаче базовый случай - это пустые строки.
Если s = "" и p = "", мы возвращаем true, так как строка полностью соответствует паттерну.
Запишем этот случай сразу:
dp[0][0] = true
dp - это матрица соответствия, в которую мы будем поэтапно вносить результаты сравнения. В ней горизонтально (колонки) идет наш паттерн p, а вертикально (строки) - строка s. Можно и наоборот, это не принципиально, главное не запутаться.
Если p.length == 0 и s.length == 0, будет true.
Пример:
s = 'aab'
p = 'c*a*b'
0 1 2 3 4 5
c * a * b
0 +
1 a
2 a
3 b
Обращаем внимание, нумерация символов будет сдвинута, так как в массиве появляется дополнительный нулевой элемент для пустой строки. Поэтому результат сравнения s[0] и p[0] будет записан НЕ в dp[0][0], а в dp[1][1]. Считаем, что это не индекс элемента в строке, а длина строки.
В рамках этой задачи возможно использование индекса -1 для обозначения пустой строки: s[-1] = "".
Заполнение матрицы
Очевидно, что нам потребуются два указателя, чтобы пройти в двойном цикле по обеим строкам и сравнить каждую пару символов.
Пусть это будет i для строки s, и j для паттерна p.
То есть это обычный двойной цикл, сочетания в котором покроют все клетки нашей матрицы.
Если символы совпадут, то совпадение всей строки будет зависеть от предыдущего результата.
Пример:
s = 'ab' p = 'ab' i j s[i] p[j] 0 0 'a' 'a' совпадение => dp[1][1] = true 0 1 'a' 'b' нет совпадения => dp[1][2] = false 1 0 'b' 'a' dp[2][1] = false 1 1 'b' 'b'
На последней итерации у нас есть совпадение, но прежде чем записать dp[2][2] = true, нужно проверить предыдущий результат (dp[1][1]). Он равен true, поэтому и сюда записываем true.
Правила заполнения
Обозначим правила, по которым мы будем сравнивать конкретные символы. Тут можно выделить 4 отдельных случая:
1) Символы одинаковые: s[i] === p[j]
Есть совпадение, нужно проверить предыдущий результат. Если он true, то и здесь будет true.
Текущее сравнение будет находиться в dp[i + 1][j + 1].
Предыдущий результат находится в dp[i ][j] - шаг назад в каждой строке.
2) В паттерне встретилась точка: p[j] === '.'
То же самое, что в предыдущем случае.
3) В паттерне встретилась звездочка: p[j] === '*'
Тут возможны два варианта:
3.1) Предыдущий символ паттерна не совпадает с текущим символом строки, получается, что звездочка соответствует нулевому количеству символов.
Сравним, например, строки "aс" и "ab*с".
Такое сравнение у нас будет при i = 1, j = 2 (сравниваем "ac" и "ab*").
Текущий символ строки - s[1] = "c", предыдущий символ паттерна - p[1] = "b". Они не равны. Получается, что фрагмент "b*" из паттерна можно выбросить.
Тогда предыдущим шагом будет сравнение "ac" и "a" - из паттерна выбрасываем сразу оба символа. Это клетка матрицы dp[i + 1][j - 1].
3.2) Предыдущий символ паттерна совпадает с текущим символом строки или предыдущий символ паттерна - точка: p[j - 1] === s[i] или p[j - 1] === '.'
Тут возможны 3 случая:
- Звездочка обозначает один символ: "ac" === "ac*". Предыдущее сравнение: "ac" и "ac", это ячейка dp[i + 1][j]
- Звездочка обозначает несколько символов: "acc" === "ac*". Предыдущее сравнение: "ac" и "ac*", это ячейка dp[i][j + 1]
- Звездочка обозначает нулевое количество символов: "ab" === "abc*". Предыдущее сравнение: "ab" и "ab", это ячейка dp[i + 1][j - 1]
Если хоть в одной из этих ячеек true, у нас совпадение в текущем сравнении: dp[i + 1][j + 1].
Самое сложное - не запутаться в этих индексах и правильно понять, где был предыдущий результат, с которым нужно сравнивать.
Заполнение первого ряда
В ряде решений предлагают сразу же заполнить первый ряд нашей матрицы (в котором s - пустая строка).
Первую колонку (где p - пустая строка) заполнять не нужно, там всегда будет false.
s = 'aab'
p = 'c*a*b'
0 1 2 3 4 5
c * a * b
0 +
1 a
2 a
3 b
i тут всегда будет -1, а s[i] = "".
Первая итерация:
j = 0
p[j] = 'c'
0 1 2 3 4 5
c * a * b
0 + -
1 a
2 a
3 b
Вторая итерация:
j = 1
p[j] = '*'
сравниваем s[i] и p[j-1]
s[i] = ''
p[j-1] = 'c'
нет совпадения, значит, * - нулевое количество
предыдущее сравнение: s[i] и p[j-1] - это dp[0][0]
оно равно true, поэтому здесь тоже true
0 1 2 3 4 5
c * a * b
0 + - +
1 a
2 a
3 b
Третья итерация:
j = 2
p[j] = 'a'
0 1 2 3 4 5
c * a * b
0 + - + -
1 a
2 a
3 b
Четвертая итерация:
j = 3
p[j] = '*'
s[i] = ''
p[j-1] = 'a'
предыдущее сравнение dp[i+1][j-1] = dp[0][2] = true
0 1 2 3 4 5
c * a * b
0 + - + - +
1 a
2 a
3 b
Пятая итерация:
j = 4
p[j] = 'b'
0 1 2 3 4 5
c * a * b
0 + - + - + -
1 a
2 a
3 b
Заполнение матрицы
Продолжим заполнять нашу матрицу для i = 0:
s = 'aab'
p = 'c*a*b'
i = 0
s[i] = 'a'
j = -1
s[0] != p[-1] // 'a' != ''
dp[1][0] = false
j = 0
s[0] != p[0] // 'a' != 'c'
dp[1][1] = false
j = 1
s[0] != p[0] // 'a' != 'c'
значит, * - нулевое количество символов
предыдущий результат: dp[1][0] // false
dp[1][2] = false
j = 2
s[0] == p[2] // 'a' == 'a'
предыдущий результат: dp[0][2] // true
dp[1][3] = true
j = 3
s[0] == p[2] // 'a' == 'a'
значит, * может означать что угодно
1) один символ: dp[1][3] // true
2) несколько символов: dp[0][4] // true
3) ни одного символа: dp[1][2] // false
dp[1][4] = true
j = 4
s[0] != p[4] // 'a' != 'b'
dp[1][5] = false
0 1 2 3 4 5
c * a * b
0 + - + - + -
1 a - - - + + -
2 a
3 b
Заполненная матрица выглядит так:
0 1 2 3 4 5
c * a * b
0 + - + - + -
1 a - - - + + -
2 a - - - - + -
3 b - - - - - +
Нас интересует правая нижняя ячейка, которая соответствует сравнению двух строк. В ней true, так что строка s соответствует паттерну p.
Сложность алгоритма: O (s.length * p.length)
Полный код:
function isMatch(s: string, p: string): boolean {
const dp = Array(s.length + 1).fill(null)
.map(() => Array(p.length + 1).fill(false));
dp[0][0] = true;
for (let i = 0; i < p.length; i++) {
if (p[i] === '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
for (let i = 0; i < s.length; i++) {
for (let j = 0; j < p.length; j++) {
const sChar = s[i];
const pChar = p[j];
if (pChar === '.' || pChar === sChar) {
dp[i + 1][j + 1] = dp[i][j];
continue;
}
if (pChar === '*') {
const prevPChar = p[j - 1];
if (prevPChar === '.' || prevPChar === sChar) {
dp[i + 1][j + 1] = dp[i][j + 1]
|| dp[i + 1][j]
|| dp[i + 1][j - 1];
} else {
dp[i + 1][j + 1] = dp[i + 1][j -1];
}
}
}
}
return !!dp[s.length][p.length]
};