Ограничения:
0 <= s.length, p.length <= 2000
s
содержит только строчные латинские буквы.p
содержит только строчные английские буквы,'?'
или'*'
.
Решение
Решение для сопоставления шаблона с подстановочными знаками включает создание двумерного логического массива dp
, где dp[i][j]
представляет, совпадают ли первые i
символов входной строки (s
) с первыми j
символами шаблона (p
) с заданными условиями подстановочных знаков. Затем массив заполняется с помощью вложенного цикла for, в котором реализована логика сопоставления символов и подстановочных знаков.
/** * @param {string} s * @param {string} p * @return {boolean} */ //Metehan Homriş var isMatch = function isMatch(s, p) { let dp = new Array(s.length + 1); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(p.length + 1).fill(false); } dp[0][0] = true; // Fill the first row for patterns that starts with '*' for (let j = 1; j <= p.length; j++) { if (p[j - 1] === '*') { dp[0][j] = dp[0][j - 1]; } } // Fill the rest of the table for (let i = 1; i <= s.length; i++) { for (let j = 1; j <= p.length; j++) { if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else if (p[j - 1] === '*') { dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; } } } return dp[s.length][p.length]; }
Функция принимает два параметра, s
и p
, которые представляют входную строку и шаблон соответственно. Он инициализирует двумерный логический массив dp
размером (s.length + 1
) x (p.length + 1
) и заполняет его значением false. Первая строка и столбец массива — это особые случаи, которые необходимо обрабатывать отдельно. Первая строка представляет случай, когда входная строка пуста, а первый столбец представляет случай, когда шаблон пуст.
Первый цикл обрабатывает особый случай, когда шаблон начинается с «*». Он устанавливает значение dp[0][j]
как истинное, если значение dp[0][j-1]
истинно. Это связано с тем, что «*» может соответствовать любой последовательности символов, включая пустую последовательность.
Вложенный цикл, начинающийся с i=1
и j=1
, заполняет остальную часть таблицы. Цикл сравнивает текущий символ во входной строке с текущим символом в образце. Если они совпадают, значение dp[i][j]
устанавливается равным значению dp[i-1][j-1]
. Если текущим символом в шаблоне является '?', он соответствует любому символу, поэтому значение dp[i][j]
устанавливается равным значению dp[i-1][j-1]
. Если текущим символом в шаблоне является '*', он может соответствовать любой последовательности символов, включая пустую последовательность, поэтому мы можем установить dp[i][j]
как истину, если либо dp[i][j-1]
, либо dp[i-1][j]
истинны. Это связано с тем, что '*' может соответствовать любой последовательности символов, включая пустую последовательность, поэтому он может либо соответствовать текущему символу во входной строке, либо не соответствовать ему вообще.
Наконец, функция возвращает значение dp[s.length][p.length]
, представляющее результат сопоставления шаблона с подстановочными знаками. Если это значение истинно, это означает, что вся входная строка соответствует шаблону, а если ложно, это означает, что входная строка не соответствует шаблону.
Автор Метехан Хомриш
Дополнительные материалы на PlainEnglish.io.
Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord.
Повысьте узнаваемость и признание вашего технического стартапа с помощью Circuit.