Вирішуємо hard-задачу з Leetcode: Regular Expression Matching

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Усім привіт, мене звати Сергій, я більше пʼятнадцяти років працюю розробником ПЗ. Працював з беком і з фронтом, з девопс, зараз працюю бекенд розробником. У цій статті пропоную розглянути вирішення задачі з Leetcode. Щоб було цікавіше, візьмемо задачу з підрозділу hard Regular Expression Matching і вирішимо її на Rust.

Відразу скажу, що перший розгляданий варіант коду не є оптимальним за швидкістю чи за памʼяттю, і ціль статті — показати ітеративно підходи до вирішення складних задач, а не створити найшвидше рішення. Оптимальніше рішення є на моєму гітхабі, і я додумався до того алгоритму вже після написання цієї статті.

Також дисклеймер: я не дивився інші рішення, ні до сабміту свого, ні після. Точно існує щось оптимальніше і простіше, що я пропустив.

Умови задачі і розгляд проблеми

Нам треба реалізувати алгоритм зіставлення рядка зі спрощеним регулярним виразом.

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).

Маємо такий синтаксис:

• a зіставляється з одним символом a. Може бути будь-який символ (у цій задачі — будь-яка маленька англійська літера), окрім . та *, які мають спеціальне значення. Зверніть увагу, що екранування підтримувати не потрібно, цього нема в умовах, і рішення проходить тести і без нього.
• . зіставляється з будь-яким одним символом. Символ обовʼязково має бути присутній, пустий рядок не рахується за збіг.
• * квантифікатор «нуль або більше». Вказує на те, що попередній символ може зустрічатися від нуля і більше разів.

Також, суттєва умова — вираз має збігатися з рядком повністю, а не з префіксом. Тобто, регулярка a*b не збігається з рядком abc. У цьому є відмінність від звичайних регулярок, які збігаються з підрядком.

Хоча задача може здатися на вигляд дуже простою (як і здалося мені с першого погляду), вона не даремно знаходиться у розділі hard, як ми далі і побачимо.

Цю задачу складно навіть просто вирішити, і ще складніше — вирішити ефективно. Складність її для мене була у тому, що є досить багато випадків, які, природно, не вказані в описі, і до яких я доходив у процесі вирішення. Також ми побачимо, що алгоритм, який може здатися досить простим і прямолінійним, не є таким.

Підготовка до вирішення

Встановлення та налаштування Rust та середовища я не буду тут описувати, все стандартно. Створюємо новий проєкт і редагуємо файл main.rs

pub struct Solution;

#[allow(dead_code)]
impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        false
    }
}

#[cfg(test)]
mod test {
    use super::Solution;

    #[test]
    fn case001() {
        assert_eq!(Solution::is_match("aa".to_string(), "a".to_string()), false);
    }
}

fn main() {
    println!("Hello, world!");
}

Запускаємо cargo test і бачимо, що наш тест «пройшов». Далі будемо додавати код і більше тест-кейсів.

Перший погляд на алгоритм і перша ітерація

Відразу скажу, що цю задачу можна вирішити за допомогою звичайних регулярних виразів, вбудованих у мову. Спрощений синтаксис є підмножиною синтаксису звичайних регулярних виразів.

Якщо зіставити вираз з рядком за допомогою вбудованих регулярних виразів, і перевірити, що збіг дорівнює вхідному рядку (щоб виконати вимогу на повне зіставлення), то ми вирішимо задачу.

Якщо вам попадеться ця задача на співбесіді — можете на це зауважити. Але вам має бути дуже потрібна саме та робота, щоб вирішувати на співбесіді hard задачі з Leetcode.

Ми реалізуємо власний алгоритм.

Можна побачити, що наш алгоритм рекурсивний. Тобто, ми беремо перший патерн з регулярного виразу, і зіставляємо його з початком рядка. Якщо вдалося зіставити, викликаємо рекурсивно алгоритм для залишку регулярки і залишку вхідної рядка. Синтаксис нашої регулярки досить простий, і ми можемо реалізувати алгоритм без look-back.

Створимо структуру для опису патерну. Тут насправді я трохи забігаю наперед, бо починав я вирішення без цієї структури, але, щоб було коротше, наводжу її одразу:

pub struct Pattern<'a> {
    pub match_char: char,
    pub allow_multiple: bool,
    pub next_regex: &'a str,
}

Структура досить проста: match_char містить символ, з яким іде зіставлення, allow_multiple — якщо після символу була зірочка *, і next_regex — це залишок регулярки.

Також оголошуємо лайфтайм ’a. Його потрібно вказувати, якщо структура містить у собі (нестатичні) посилання (&). Цей лайфтайм підкаже компілятору, що структура не має «пережити» дані, на які є посилання всередині неї (тобто дані, на які ми посилаємося, не можна видалити раніше, ніж структуру).

Також наведу функцію, яка створює цю структуру з рядка:

fn next_pattern<'a>(regex: &'a str) -> Option<Pattern<'a>> {
    let mut next_index = 1;
    let mut chars = regex.chars();

    let next_char = chars.next();
    if next_char.is_none() {
        return None;
    }

    let match_char = next_char.unwrap();

    let allow_multiple = chars.next().unwrap_or_default() == '*';
    if allow_multiple {
        next_index = next_index + 1;
    }

    Some(Pattern {
        match_char,
        allow_multiple,
        next_regex: &regex[next_index..],
    })
}

Вона має бути всередині impl Solution. Ми не будемо розглядати у деталях, як вона працює, тому що вона досить проста і не має безпосереднього стосунку до задачі.

На що тут варто звернути увагу?

По-перше, функція приймає &str. Це слайс — вказівник на діапазон значень всередині рядка або масиву. Це невеличка оптимізація, яка дозволяє мати у памʼяті один екземпляр рядка з регуляркою і не створювати нових строк для кожного залишку патерну (і не копіювати зайвий раз).

По-друге, функція має лайфтайм, який використовується як у параметрі, так і у типі результату. Це означає, що структура, яку поверне функція, буде мати всередині посилання на слайс, переданий у функцію. Слайс, у свою чергу, це посилання на строку + пара індексів (початок і кінець), тобто ми маємо на усю програму два масиви байтів (на інпут і патерн), які не копіюємо.

По-третє, функція повертає Option. Це алгебраїчний тип для (можливо) відсутнього значення. Ми повернемо None, коли дійдемо до кінця регулярки.

Тепер, напишемо сігнатуру-заготовку для нашого рекурсивного алгоритму.

fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
    false
}

і викличемо її:

pub struct Solution;

#[allow(dead_code)]
impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        return Self::match_recursive(s.as_str(), None);
    }

    fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
        false
    }

    fn next_pattern<'a>(regex: &'a str) -> Option<Pattern<'a>> {
        let mut next_index = 1;
        let mut chars = regex.chars();

        let next_char = chars.next();
        if next_char.is_none() {
            return None;
        }

        let match_char = next_char.unwrap();

        let allow_multiple = chars.next().unwrap_or_default() == '*';
        if allow_multiple {
            next_index = next_index + 1;
        }

        Some(Pattern {
            match_char,
            allow_multiple,
            next_regex: &regex[next_index..],
        })
    }
}

pub struct Pattern<'a> {
    pub match_char: char,
    pub allow_multiple: bool,
    pub next_regex: &'a str,
}

#[cfg(test)]
mod test {
    use super::Solution;

    #[test]
    fn case001() {
        assert_eq!(Solution::is_match("aa".to_string(), "a".to_string()), false);
    }
}

fn main() {
    println!("Hello, world!");
}

Поки що наше рішення нічого не робить, але ми підготували оточення для подальшої реалізації. Це дуже важливо — мати щось, що можна запустити і протестити, навіть якщо воно не працює. Це дозволить швидко перевіряти різні варіанти кода і робити маленькі зміни, які просто оцінити і перевірити.

Початок реалізації

Загалом, як я вже казав, алгоритм буде виглядати майже як посимвольне перевіряння вхідної рядка за допомогою патерну.

Запишемо початок рекурсії:

pub fn is_match(s: String, p: String) -> bool {
    let first_pattern = Self::next_pattern(p.as_str());
    return Self::match_recursive(s.as_str(), first_pattern);
}

fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
    if let Some(pattern) = p {
        false
    } else {
        return s.len() == 0;
    }
}

Тут ми заодно реалізували перевірку, чи охопив патерн усю строку. Якщо регулярка скінчилася, а рядок ні, то рядок не збігся з патерном, і ми повернемо false.

Зіставлення одного символу

Наступним кроком реалізуємо зіставлення одного фіксованого символу. Це вже корисний код, який вирішує частину наших вимог:

fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
    if let Some(pattern) = p {
        let next_char = s.chars().next();

        if let Some(next) = next_char {
            if next == pattern.match_char {
                return Self::match_recursive(&s[1..], Self::next_pattern(pattern.next_regex));
            } else {
                return false;
            }
        } else {
            return false;
        }
    } else {
        return s.len() == 0;
    }
}

Ми отримуємо наступний символ вхідного рядка і порівнюємо його з патерном.

По-перше, наступного символу може і не бути. Це значить, що ми добігли кінця рядка, але в нас ще залишилися патерни для зіставлення. Тоді ми одразу повертаємо false. Це не зовсім вірно у загальному випадку, пустий рядок — це цілком коректний інпут, але для частини, яку ми реалізуємо — зіставлення лише одного символу без квантифікаторів — це буде коректно.

По-друге, якщо символ є, але не сходиться — повертаємо false. Це вже не спрощення, так і має бути.

І, по-третє, якщо символ зійшовся, то викликаємо рекурсивно алгоритм для наступного патерна і залишку рядка.

Також, додамо декілька тест-кейсів:

#[cfg(test)]
mod test {
    use super::Solution;

    #[test]
    fn case001() {
        assert_eq!(Solution::is_match("aa".to_string(), "a".to_string()), false);
    }

    #[test]
    fn case002() {
        assert_eq!(Solution::is_match("aa".to_string(), "aa".to_string()), true);
    }

    #[test]
    fn case003() {
        assert_eq!(Solution::is_match("ab".to_string(), "ab".to_string()), true);
    }

    #[test]
    fn case004() {
        assert_eq!(Solution::is_match("".to_string(), "".to_string()), true);
    }

    #[test]
    fn case005() {
        assert_eq!(Solution::is_match("a".to_string(), "".to_string()), false);
    }

    #[test]
    fn case006() {
        assert_eq!(Solution::is_match("".to_string(), "a".to_string()), false);
    }

    #[test]
    fn case007() {
        assert_eq!(Solution::is_match("b".to_string(), "a".to_string()), false);
    }

    #[test]
    fn case008() {
        assert_eq!(
            Solution::is_match("ab".to_string(), "ac".to_string()),
            false
        );
    }
}

Усі тести проходять.

Також тривіально додаємо підтримку для . (будь-який символ):

...

    if pattern.match_char == '.' || next == pattern.match_char {

...

І тест-кейси.

#[test]
fn case009() {
    assert_eq!(Solution::is_match("ab".to_string(), "a.".to_string()), true);
}

#[test]
fn case010() {
    assert_eq!(
        Solution::is_match("abcd".to_string(), "....".to_string()),
        true
    );
}

#[test]
fn case011() {
    assert_eq!(
        Solution::is_match("abcd".to_string(), "...".to_string()),
        false
    );
}

Проста частина позаду. Як бачимо, головне — підготувати код до ітеративних змін, забезпечити просте написання та виклик тестів, писати як позитивні, так і негативні тест-кейси, і не намагатися одразу писати 100% правильний код.

Видалення і виправлення — це нормально, і це суть ітеративної розробки.

Зіставлення з повторюваннями

Нагадаю, якщо після символу (у тому числі і .) іде зірочка *, то це означає, що символ може зустрічатися нуль або більше разів. Саме ця умова є найскладнішою у цьому завданні, і саме з цією умовою повʼязана купа неочевидних тест-кейсів, на які я витратив найбільше часу.

Це завдання на Leetcode має понад 450 тест-кейсів, що може дати вам уяву, скільки там тонкощів і різних граничних умов.

На перший погляд, усе досить просто. Спочатку додамо декілька тест-кейсів:

#[test]
fn case012_match_multiple() {
    assert_eq!(
        Solution::is_match("aaad".to_string(), "a*d".to_string()),
        true
    );
}

#[test]
fn case013_match_multiple_to_one() {
    assert_eq!(
        Solution::is_match("ad".to_string(), "a*d".to_string()),
        true
    );
}

#[test]
fn case014_match_mutiple_to_zero() {
    assert_eq!(Solution::is_match("d".to_string(), "a*d".to_string()), true);
}

Бачимо, що вони валяться, окрім case013_match_multiple_to_one, який, по суті, покривається уже реалізованою логікою, а тому не валиться.

Додамо просту реалізацію:

fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
    if let Some(pattern) = p {
        let next_char = s.chars().next();

        if pattern.allow_multiple {
            false
        } else {
            if let Some(next) = next_char {
                if pattern.match_char == '.' || next == pattern.match_char {
                    return Self::match_recursive(
                        &s[1..],
                        Self::next_pattern(pattern.next_regex),
                    );
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
    } else {
        return s.len() == 0;
    }
}

Логіку для зіставлення з одним символом ми вже написали і потестили, тому робимо if, і залишаємо попередній код у else.

Поки що відразу повертаємо false, тестимо, тепер усе вірно, і нереалізовані тести валяться.

Пишемо реалізацію:

if let Some(next) = next_char {
    if pattern.match_char == '.' || next == pattern.match_char {
        return Self::match_recursive(&s[1..], Some(pattern));
    } else {
        return Self::match_recursive(&s, Self::next_pattern(pattern.next_regex));
    }
} else {
    return Self::match_recursive(&s, Self::next_pattern(pattern.next_regex));
}

По-перше: пустий вхідний рядок — цілком коректний інпут для регекса із зірочкою. Якщо ми не можемо прочитати наступний символ рядка, то викликаємо зіставлення далі.

Цим ми обробимо патерни типу abc* на рядках ab.

Додамо ці тест-кейси:

#[test]
fn case015_match_mutiple_at_the_end_string() {
    assert_eq!(
        Solution::is_match("ab".to_string(), "abc*".to_string()),
        true
    );
}

#[test]
fn case016_match_several_mutiple_at_the_end_string() {
    assert_eq!(
        Solution::is_match("ab".to_string(), "abc*d*e*".to_string()),
        true
    );
}

Все працює.

Здавалося б, готово, але давайте спочатку перевіримо, чи буде працювати такий патерн на початку рядка:

#[test]
fn case017_match_several_at_the_start_of_string() {
    assert_eq!(
        Solution::is_match("bc".to_string(), "a*bc".to_string()),
        true
    );
}

#[test]
fn case018_match_multiple_several_at_the_start_of_string() {
    assert_eq!(
        Solution::is_match("de".to_string(), "a*b*c*de".to_string()),
        true
    );
}

Працює. Спробуємо засабмітити, і тут нас чекає...

Wrong answer

Input: s = «aaa»
Pattern: p = «a*a»
Expected: true
Output: false

У чому ж помилка? Річ у тім, що наш алгоритм «жадібний». Він зіставляє патерн, доки він зіставляється, максимальну кількість разів. У нашому випадку це призводить до того, що перший же a* добігає кінця рядка, і у патерні залишається a, яке зіставляється з порожнім рядком.

Тобто інколи нам треба зупинити «жадібність» алгоритму, навіть якщо є можливість зіставляти далі. Це і є сама складна частина задачі. Я перепробував декілька ідей:

• перевіряв наступний патерн, і якщо його символ такий самий, як і у попереднього, то пропускав, якщо попередній зіставився хоча б з одним символом. Це валилося на зіставленнях патернів типу a*aa з рядком aaaaa, бо там символів більше, ніж один. Генералізація цього випадку для n символів після патерну із зірочкою теж не допомогла, бо є випадки типу патерн a*b*c*abc і рядка abcabc;
• думав перевіряти з початку, а потім ще з кінця, але це по суті те саме. Також пізніше знайшов тест-кейси, де це не спрацює, наприклад .*abc.* на рядку aaaaaaaa.

Розвʼязання

Що точно спрацює? І як взагалі цей алгоритм повинен перевіряти, щоб покрити усі випадки?

Спочатку додамо декілька тест-кейсів:

#[test]
fn case019_match_all() {
    assert_eq!(Solution::is_match("ab".to_string(), ".*".to_string()), true);
}

#[test]
fn case020() {
    assert_eq!(
        Solution::is_match("abc1111111d".to_string(), "a.c.*d".to_string()),
        true
    );
}

#[test]
fn case021() {
    assert_eq!(
        Solution::is_match("aa".to_string(), "a.*a".to_string()),
        true
    );
}

#[test]
fn case022_leetcode_test_case() {
    assert_eq!(
        Solution::is_match("mississippi".to_string(), "mis*is*ip*.".to_string()),
        true
    );
}

#[test]
fn case023_non_greedy() {
    let result = Solution::is_match("ab".to_string(), ".*c".to_string());
    assert_eq!(result, false);
}

#[test]
fn case024_regex_longer() {
    let result = Solution::is_match("aaa".to_string(), "aaaa".to_string());
    assert_eq!(result, false);
}

#[test]
fn case025_stop_char_same_as_pattern() {
    let result = Solution::is_match("aaa".to_string(), "a*a".to_string());
    assert_eq!(result, true);
}

#[test]
fn case026_multiple_zero_patterns() {
    let result = Solution::is_match("aaa".to_string(), "ab*a*c*d*e*f*a".to_string());
    assert_eq!(result, true);
}

#[test]
fn case027_simplest_zero_pattern() {
    let result = Solution::is_match("aa".to_string(), "a*a".to_string());
    assert_eq!(result, true);
}

#[test]
fn case028_simplest_zero_pattern_interaction() {
    let result = Solution::is_match("aa".to_string(), "a*b*a".to_string());
    assert_eq!(result, true);
}

#[test]
fn case029_fucked_up_lookup() {
    let result = Solution::is_match("aaacacaab".to_string(), ".*ab".to_string());
    assert_eq!(result, true);
}

#[test]
fn case030_zero_or_more_at_the_end() {
    let result = Solution::is_match("a".to_string(), "ab*".to_string());
    assert_eq!(result, true);
}

Деякі з них вигадані, деякі я додавав з літкодівських тест-кейсів, які у мене валилися. (Зрозуміло, що кожен літкодівський тест-кейс, який у вас не пройшов, треба додавати до своїх тест-кейсів.)

Так який же універсальний код зможе точно зіставити будь-який патерн, най і не з найкращим перформансом? Це, звісно, брутфорс.

Коли у нас у регексі є патерн із зірочкою, то ми не можемо знати точно, коли зупинитися. Ми можемо додати деякі еврістики, але у загальному випадку точно знати ми не можемо.

Тому, у нашому коді, коли ми перевіряємо патерн із зірочкою і він збігається, нам потрібно перевірити насправді два випадки: перший — це залишок рядка з тим же патерном, і другий — це залишок рядка з наступним патерном. Бо навіть збіжний символ може бути насправді кінцем патерну.

Напишемо код:

if pattern.allow_multiple {
    if let Some(next) = next_char {
        if pattern.match_char == '.' || next == pattern.match_char {

            // Here we add
            let is_matching_if_end_of_greed =
                Self::match_recursive(&s, Self::next_pattern(pattern.next_regex));

            if is_matching_if_end_of_greed {
                return true;
            }
            // end of add

            return Self::match_recursive(&s[1..], Some(pattern));
        } else {
            return Self::match_recursive(&s, Self::next_pattern(pattern.next_regex));
        }
    } else {
        return Self::match_recursive(&s, Self::next_pattern(pattern.next_regex));
    }
}
...

Спробуємо трохи оптимізувати.

Перше, що спадає на думку — обробляти ситуацію типу a*b, коли патерн із зірочкою не є . (будь-який символ), і наступний патерн є «один точний символ» (b), і символи у патернах різні. У цьому випадку ми знаємо точно, коли співпадіння повинно зупинитися.

Напишемо код:

fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
    if let Some(pattern) = p {
        let next_char = s.chars().next();

        if pattern.allow_multiple {
            let maybe_next_pattern = Self::next_pattern(pattern.next_regex);

            if let Some(next) = next_char {
                if pattern.match_char == '.' || next == pattern.match_char {
                    if pattern.match_char == '.'
                        || maybe_next_pattern
                            .as_ref()
                            .map(|n| {
                                n.allow_multiple
                                    || n.match_char == '.'
                                    || n.match_char == pattern.match_char
                            })
                            .unwrap_or(false)
                    {
                        let is_matching_if_end_of_greed =
                            Self::match_recursive(&s, maybe_next_pattern);

                        if is_matching_if_end_of_greed {
                            return true;
                        }
                    }

                    return Self::match_recursive(&s[1..], Some(pattern));
                } else {
                    return Self::match_recursive(&s, maybe_next_pattern);
                }
            } else {
                return Self::match_recursive(&s, maybe_next_pattern);
            }
        } else {
            if let Some(next) = next_char {
                if pattern.match_char == '.' || next == pattern.match_char {
                    return Self::match_recursive(
                        &s[1..],
                        Self::next_pattern(pattern.next_regex),
                    );
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
    } else {
        return s.len() == 0;
    }
}

Тепер бʼє 16,30% по швидкості, але 96,3% по памʼяті.

Не радіємо завчасно, тому що використання памʼяті дуже різниться від одного запуска до іншого, навіть якщо сабмітити той самий код декілька разів, споживання памʼяті може різнитися від 10% до 90% від інших. Схоже, що Leetcode не робить тести на навантаження, і на таких маленьких обсягах памʼяті похибка більша, ніж саме споживання.

Інша оптимізація — це замість рядка працювати зі слайсом (масивом) байт, за умовами у вхідному рядку і у патерні мають бути лише англійські літери. Рядки у Rust юнікоді, і один символ може складатися з декількох байтів. Ітератор &str::chars() виконує пошук мультибайтових символів і працює повільніше, ніж ітератор по масиву байт, який просто збільшує вказівник.

impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        let first_pattern = Self::next_pattern(p.as_bytes());
        return Self::match_recursive(s.as_bytes(), first_pattern);
    }

    fn match_recursive<'a>(s: &[u8], p: Option<Pattern<'a>>) -> bool {
        if let Some(pattern) = p {
            let next_char = s.iter().next();

            if pattern.allow_multiple {
                let maybe_next_pattern = Self::next_pattern(pattern.next_regex);

                if let Some(next) = next_char {
                    if pattern.match_char == b'.' || *next == pattern.match_char {
                        if pattern.match_char == b'.'
                            || maybe_next_pattern
                                .as_ref()
                                .map(|n| {
                                    n.allow_multiple
                                        || n.match_char == b'.'
                                        || n.match_char == pattern.match_char
                                })
                                .unwrap_or(false)
                        {
                            let is_matching_if_end_of_greed =
                                Self::match_recursive(&s, maybe_next_pattern);

                            if is_matching_if_end_of_greed {
                                return true;
                            }
                        }

                        return Self::match_recursive(&s[1..], Some(pattern));
                    } else {
                        return Self::match_recursive(&s, maybe_next_pattern);
                    }
                } else {
                    return Self::match_recursive(&s, maybe_next_pattern);
                }
            } else {
                if let Some(next) = next_char {
                    if pattern.match_char == b'.' || *next == pattern.match_char {
                        return Self::match_recursive(
                            &s[1..],
                            Self::next_pattern(pattern.next_regex),
                        );
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        } else {
            return s.len() == 0;
        }
    }

    #[inline]
    fn next_pattern<'a>(regex: &'a [u8]) -> Option<Pattern<'a>> {
        let mut next_index = 1;
        let mut chars = regex.iter();

        let next_char = chars.next();
        if next_char.is_none() {
            return None;
        }

        let match_char = next_char.unwrap();

        let allow_multiple = *(chars.next().unwrap_or(&b' ')) == b'*';
        if allow_multiple {
            next_index = next_index + 1;
        }

        Some(Pattern {
            match_char: *match_char,
            allow_multiple,
            next_regex: &regex[next_index..],
        })
    }
}

#[derive(Debug)]
pub struct Pattern<'a> {
    pub match_char: u8,
    pub allow_multiple: bool,
    pub next_regex: &'a [u8],
}

Тепер по швидкості додалося десь 10%, стало 25,19%. Пропоную забити і зупинитися на цьому.

Я думаю, що навряд чи ми значно пришвидшимося, доки використовуємо рекурсивний алгоритм. Його використання дозволило нам тривіально реалізувати брут-форс зіставлення, з досить зрозумілим кодом. Циклічна версія алгоритму виглядала б досить монструозно, як на мене. Тим більше, що основна причина повільності у перевірянні кожного підрядка. Вочевидь, перевіряти кожен підрядок непотрібно, така реалізація є на моєму гітхабі, але обʼєм та складність коду там на порядок більша.

Також не впевнений, що можна поміняти цей код так, щоб спрацювали tail recursion або tail call оптимізації (та і взагалі далеко не факт, що літкод запускає з потрібними прапорцями).

Тому, скоріш за все, швидші реалізації просто додумалися до кращого алгоритму (як і я, зрештою).

Наш алгоритм проходить тести літкоду лише тому, що там є обмеження по довжині як вхідної рядка (20 символів), так і патерну (30 символів). Використання його на довгих рядках або довгих патернах призведе до «комбінаторного вибуху» рекурсивних перевірок.

Вже після написання статті я додумався до іншого алгоритму, який є кращим внаслідок зменшення кількості непотрібних рекурсивних викликів.

Кращий алгоритм

Патерн ділиться на частини, які складаються з поряд розташованих однотипних патернів (тільки фіксовані або тільки повторювані патерни, які йдуть підряд).

Наприклад, у патерні ab*c*de ми могли б виділити такий набір патернів:

• a (фіксований патерн);
• b*c* (два повторюваних патерна);
• de (два фіксованих патерна);

Згрупуємо їх так, щоб у нас утворилися пари «повторюваний патерн + фіксований патерн» (кожен з них може бути відсутній). Візьмемо довший патерн для більшої наочності:

abc*d*efg*h*ijklmn*

• None + ab
• c*d* + ef
• g*h* + ijklm
• n* + None

Тепер робимо наступне: беремо першу пару патернів і шукаємо у рядку усі входження фіксованого патерну (через аналог метода index of, який вміє шукати по патерну і враховує спеціальне значення крапки .).

Якщо не знайшли, повертаємо false, бо рядок не має входження фіксованого патерну.

Далі для кожного входження беремо підрядок від початку інпуту до позиції фіксованого патерну і перевіряємо його на збіг з повторюваним патерном з пари.

Підрядки, які не зійшлися, ми пропускаємо. Якщо ж рядок зійшовся, то ми беремо частину інпут рядка, яка знаходиться після фіксованого патерну, і викликаємо рекурсивну перевірку з наступним патерном.

Якщо пара не містить повторюваного патерну, перевіряємо на збіг з початком рядка (це може бути перша пара патернів). Якщо пара не містить фіксованого патерну, перевіряємо залишок до кінця рядка (буває наприкінці рядка).

Приклад

Наприклад, хай у нас є патерн .*a та рядок bbbabba. Пара патернів у нас така: повторюваний .* і фіксований a.

• Шукаємо перше входження фіксованого патерну, це індекс 3:
  • рядок до фіксованого патерну bbb;
  • Залишок рядка bba, залишок патерну "" (порожній рядок);
    • Збігу немає, бо залишок рядка не сходиться з патерном;
• Наступне входження фіксованого патерну — це індекс 6:
  • рядок до фіксованого патерну bbbabb, сходиться з повторюваним патерном;
  • Залишок рядка і патерну — пусті рядки, тому маємо збіг.

Оцінка складності алгоритмів

У другому алгоритмі все ще є комбінаторна перевірка, але значно ефективніша, яка залежить лише від кількості входжень фіксованого патерну у залишок рядка, а не від довжини рядка, який сходиться з повторюваним патерном.

Реалізація цього алгоритму бʼє 100% за швидкістю і 60% відсотків за памʼяттю, але має на порядок більший обʼєм коду і кончені алгоритми з кучею граничних умов. Ця стаття вийшла і так дуже довгою, якщо буде цікаво, реалізацію можна побачити у репозиторії на гітхабі.

Спробуємо оцінити складність першого алгоритму.

Перевірка фіксованого патерну це О(1).

Якщо у нас є один повторюваний патерн, перевірка рядка з ним буде O(N!), де N — це довжина рядка, яка збігається з повторюваним патерном. Якщо у нас декілька патернів, то перевірка кожного це буде N!, але N це буде не повна довжина рядка, а залишок довжини, який ми перевіряємо. Тобто приблизно O(k*N!).

Не зовсім впевнений, що правильно оцінив складність алгоритму, але видно, що алгоритм потенційно дуже повільний.

Другий алгоритм набагато простіший.

Перевірка рядка на збіг з повторюваним патерном у ньому O(N), де N — це довжина рядка. Пошук фіксованого патерну — це O(N).

По-третє, кількість рекурсивних викликів залежить від кількості входження фіксованого патерну, яке не може бути більше, ніж N (довжина рядка).

Тобто, маємо O(N^2), а насправді скоріш за все O((N/2)^2), навіть у гіршому випадку. У кращому випадку буде майже лінійний алгоритм, у той час, як перший алгоритм буде факторіал при достатньо довгій частині рядка, яка збігається з повторюваними патернами.

Поради для успішного проходження тестів

• 50% успіху вирішення задачі — це підготовка оточення, у якому можна швидко і зручно писати і запускати тести, а також пробувати різні варіанти і відкочувати зміни (тому хороша ідея створити локальний гіт-репозиторій і комітити туди).
• Щоб не витрачати час тестування на налаштування оточення, краще це зробити заздалегідь. Сайти з тестами влаштовані досить схоже, тому навіть якщо ви не знаєте, яка буде структура, підготуйте хоча б таку, як у літкоді. Адаптувати буде швидше, ніж зробити з нуля.
  У випадку Rust усе робиться швидко, але для інших мов може зайняти 5-10 хвилин, які можуть виявитися далеко не зайвими у кінці.
• Пишіть код у IDE, до якої ви звикли, за можливості. Варто поцікавитися у інтервʼюера, чи можна це робити. Деякі компанії (а також деякі сайти з тестами) забороняють перемикати вкладки браузера та перемикатися на інші програми. У цьому випадку можна запропонувати зробити запис свого екрану, як альтернативу. Не всі на це погодяться, тому що хочуть обробляти результати тестування (напів)автоматично, і хочуть одразу відкидати типу «читерів» (тих, хто перемикався).
  Звісно, велике питання, чи варто взагалі витрачати час на тести для компанії, яка вимагає написання такого, досить важкого навіть у звичному оточенні, тесту у браузері.
• Може, це досить очевидно, але головне — по-перше, зрозуміти умови задачі, а по-друге — створити алгоритм. Написати код по готовому алгоритму значно простіше, ніж зразу писати в надії створити алгоритм на ходу.
• Також не нехтуйте категорією складності задачі. Якщо на літкоді вона відноситься до складних, то вона, напевно, і є складна, і якщо алгоритм знайшовся легко і просто, то тричі подумайте і перевірте, чи справді алгоритм підходить і вирішує задачу, зекономите час на написання.
• Одразу можна зробити функції та структури (а також написати до них тести), які точно підійдуть до будь-якого алгоритму. У нашому випадку це структура з патерном та функція парсингу наступного патерну з рядка.
• Варто запитати у інтервʼюера, що для нього важливіше: перформанс чи чистий код. Також запитайте, якої складності він очікує алгоритм, деякі завдання мають тривіальні розвʼязання зі складністю O(n^2), і набагато складніші з меншою складністю.
• Тренуйтесь вирішувати алгоритмічні задачі. Це окремий вид програмування, особливо якщо є обмеження по складності/ памʼяті, або обмежений час на вирішення. Не маючи звички, можна завалити такий тест навіть прекрасно вміючи програмувати. Тому підготуйтесь, вирішіть кілька задач, най навіть з категорії легких.