The программирование, часть вторая

Усилиями 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()

)

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