leetcode'овские задачки

Дан список емейлов, в котором у пользователей могут быть точки в любом месте имени, плюс хвостик +что-то, но только в части до домена @. Гарантируется, что левая-правая часть существует, и есть точно один '@'. Задача - посчитать уникальные email'ы.

Это прямо референсная задача для "пощупать match".

Я всё ещё слегка неловко ощущаю в районе map/reduce растового исполнения, хотя он тут просится.

use std::collections::{HashSet};
#[derive(Clone,Copy)]
enum Part{
    Local,
    Tail,
    Domain
}
fn normalize(email: &String) -> String{
    let mut part = Part::Local;
    let mut output = String::with_capacity(email.len());
    for s in email.chars(){
        output.push(
            match (part, s) {
                (Part::Domain, _)  => s,
                (_, '@') => {
                    part = Part::Domain;
                    s
                },
                (Part::Tail, _) => {continue},
                (Part::Local, '.') => {continue},
                (Part::Local, '+') => {
                    part = Part::Tail;
                    continue
                },
                (Part::Local, _) => s
            }
        )
    }
    output
}

impl Solution {
    pub fn num_unique_emails(emails: Vec<String>) -> i32 {
        let mut uAddr: HashSet<String> = HashSet::with_capacity(emails.len());
        for email in emails.iter(){
            uAddr.insert(normalize(email));
        }
        uAddr.len() as i32
    }
}

Особенно офигенно тут использование continue в середине выражения match. Оно строго правильное по типу и говорит, что результат выражения - bottom type (unreachable code), так что в push в этом случае управление не попадает.

Rust-строковое

А вот строки в Rust'е неожиданно сложны. Например, такая простая вещь, как strstr() (поиск начала подстроки в строке) с каждой итераций раздумий всё сложнее и сложнее. Особенно, если делать эффективно.

Во-первых, мы не можем иметь индекс в строку, потому что размер символа в строке плавает. Во-вторых любые байтовые операции не применимы для вычисления индекса, потому что байты в индекс превращаются нетривиальным образом.

Итератор chars не очень хороший, потому что он из любого символа (даже 1-байтового) делает 4 байта. Это значит, что для поиска подстроки в гигабайтной строке нам нужно будет перемолотить 4 ГБ в режиме записи (вероятнее всего, в регистр, но всё равно...)

Т.е. первая задача, которая у нас будет, это реализация считающего Window поверх String/str без копирования. Внутри это указатель на первый символ и байтовая длина (при том, что количество символов в window фиксировано, байтовый размер будет прыгать очень неровно).

Основываться она должна на str-итераторе по символам. Такой итератор получает &str, после чего начинает возвращать &str в один символ (in-place, без копирования!). Т.е. ещё уровнем ниже, это fat pointer на байты строки, который указывает на начало символа и содержит в себе его длину, кроме того, он содержит в себе (для удобства, видимо), адрес начала строки, и её оригинальный размер.

Перед тем, как изобретать всё своё с нуля, надо ещё раз перечитать что String и str умеют из коробки (игнорируя существование find и matches, разумеется).

Чем глубже я в это погружаюсь, тем тоньшее все нюансы становятся. Я чувствую, что пока что я сделаю очень грубо, с использованием Vec.

.. Сделал. Получил заслуженные 40мс (нижние 27% всех решений). Нырять в устройства fat pointers я пока не готов.

pub fn str_str(haystack: String, needle: String) -> i32 {
    if needle.len() == 0 {return 0};
    let haystack_vec: Vec<char> = haystack.chars().collect();
    let needle_vec: Vec<char> = needle.chars().collect();
    let mut pos = 0;
    for candidate in haystack_vec.windows(needle_vec.len()){
        if candidate == needle_vec.as_slice(){
            return pos as i32;
        }
        pos += 1;
    }
    -1
}