I'm practicing Exercism's Rust Track. One of the questions is as follows:
An anagram is a rearrangement of letters to form a new word.
Given a word and a list of candidates, select the sublist of anagrams of the given word.Given
"listen"
and a list of candidates like"enlists" "google" "inlets" "banana"
the program should return a list containing
"inlets"
.The solution is case insensitive, which means
"WOrd"
is the same as"word"
or"woRd"
. It may help to take a peek at the std library for functions that can convert between them.The solution cannot contain the input word. A word is always an anagram of itself, which means it is not an interesting result. Given
"hello"
and the list["hello", "olleh"]
the answer is["olleh"]
.You are going to have to adjust the function signature provided in the stub in order for the lifetimes to work out properly. This is intentional: what's there demonstrates the basics of lifetime syntax, and what's missing teaches how to interpret lifetime-related compiler errors.
Try to limit case changes. Case changes are expensive in terms of time, so it's faster to minimize them.
If sorting, consider
sort_unstable
which is typically faster than stable sorting. When applicable, unstable sorting is preferred because it is generally faster than stable sorting and it doesn't allocate auxiliary memory.
My code, that works and passes all test cases, is as follows:
use std::collections::{hash_map::HashMap, HashSet};
pub fn anagrams_for<'a>(word: &str, possible_anagrams: &[&'a str]) -> HashSet<&'a str> {
let mut freq_map: HashMap<String, u32> = HashMap::new();
let mut indices: Vec<String> = Vec::new();
word.chars().for_each(|ch| {
let c = to_lowercase_if_not_already(ch);
*freq_map.entry(c.clone()).or_default() += 1;
indices.push(c);
});
possible_anagrams
.iter()
.filter(|candidate| {
if word.len() != candidate.len() {
false
} else {
let (ana, same) = is_anagram(&freq_map, &indices, candidate);
!same && ana
}
})
.cloned()
.collect()
}
fn to_lowercase_if_not_already(ch: char) -> String {
if ch.is_uppercase() {
ch.to_lowercase().to_string()
} else {
ch.to_string()
}
}
fn is_anagram(
freq_map: &HashMap<String, u32>,
indices: &[String],
candidate: &str,
) -> (bool, bool) {
let mut f_map: HashMap<String, u32> = HashMap::new();
let mut score = freq_map.len();
let mut same = true;
for (i, ch) in candidate.chars().enumerate() {
let c = to_lowercase_if_not_already(ch);
if !freq_map.contains_key(&c) || f_map.get(&c) == freq_map.get(&c) {
return (false, false);
}
*f_map.entry(c.clone()).or_default() += 1;
if f_map[&c] == freq_map[&c] {
score -= 1;
}
same &= c == indices[i];
}
(score == 0, same)
}
However, I'm little bothered by the use of clone
and cloned
. I've a feeling that this is a case for Rc, although I'm not sure how. Any advice?