amarao

Усилиями r/rust с Реддита (note: реддит живее, чем SO, причём не только в программировании) проблема quick fail была решена, причём идиоматически. Исчезли две аллокации (из четырёх), и как мне кажется, алгоритмически его быстрее уже не сделать. (Да, я понимаю про идею использовать буквы из шаблона как индексы, но на практике это потребует аллокации вектора букв, и врят ли будет лучше).

Задача: https://leetcode.com/problems/word-pattern/submissions/

В двух словах: дана строка из букв и из слов, надо ответить, эквивалентны ли они друг другу в режиме "шаблона" : "aab" эвивалентна "dog dog cat", "abca" эвивалентна "foo bar baz foo".

(предыдущее обсуждение и текст полный задачи: https://amarao.dreamwidth.org/45539.html)

К предыдущему решению претензия была в отсутствии quick fail, то есть если с самого начала строки различаются, старый алгоритм продолжал "варить" до упора. (aaaaaaaaaaa и "foo bar bar bar bar bar"). Плюс, две аллокации для output.

r/rust был более чем любезен указать на две важные детали:

1. Можно возвращать итераторы вместо векторов.
2. Итераторы лего сравнить.

Кроме того, можно требовать не Iterator, а IntoIterator, так что можно передать любой "итрабельный" объект без вызова его iter(), хотя в конкретном этом случае это не работает, потому что итераторы у строки и шаблона разные и странные (split_whitespace и chars).

Получившийся код для меня находится чуть выше моего свободного понимания Rust: я его могу прочитать, но второй такой же не напишу (или уже напишу после этой истории?):

use std::hash::Hash;
use std::collections::HashMap;

impl Solution {
    fn abstract_iterator(input: impl IntoIterator<Item = impl Hash + Eq>) -> impl Iterator<Item = usize> 
    {
        let mut dict = HashMap::new();
        input
            .into_iter()
            .map(move |elem| {
                let id = dict.len();
                *dict.entry(elem).or_insert(id)
        })
    }

    pub fn word_pattern(pattern: String, s: String) -> bool {
        Self::abstract_iterator(pattern.chars()).eq(
            Self::abstract_iterator(s.split_whitespace())
        )
    }
}

Глядя на этот код, мне немного не нравится word_pattern своей некрасивостью.

Наверное, лучше было бы написать свой трейт, чтобы функция стала такой:

        pattern
            .chars()
            .abstract_iterator()
            .eq(
               s
                .split_whitespace()
                .abstract_iterator()
             )

Но в целом - это огонь. Это совсем не похоже на "низкоуровневый язык,
соревнующийся С++ за системность и поглядывающий на лавры С".