Rust dynamic programming : word break

Question

I've solved this problem: https://leetcode.com/problems/word-break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1:

impl Solution {
    fn dfs(i: usize, words: &HashSet<String>, cur_word: &str, cache: &mut HashMap<usize, bool>, n: usize, orig:&str) -> bool {

        if i == n {
            return true;
        }
        if cache.contains_key(&i) {
            return *cache.get(&i).unwrap();
        }
        if words.contains(cur_word) {
            cache.insert(i, true);
            return true;
        }
        let mut res = String::from("");
        for k in i..n {
            let s = orig.chars().nth(k).unwrap();
            res.push(s);
            if words.contains(&res) && Self::dfs(k + 1, &words, orig.get(k+ 1..).unwrap_or_default(), cache, n, orig) {
                cache.insert(i, true);
                return true;
            }
        }
        cache.insert(i, false);
        return false;
    }
    pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
        let set = word_dict.into_iter().collect::<HashSet<String>>();
        let mut cache = HashMap::new();
        Self::dfs(0, &set, "", &mut cache, s.len(), &s)
    }
}

Please ignore the useless Solution struct -- that's part of the website's interface for solution.

I'm quite upset with how my dfs function is structured -- I am passing far too many arguments into it.

In python, I would've simply created a recursive nested function, which would have captured outer variables; rust doesn't allow for recursive closures, as a closure is an unnamed struct. So I've had to resort to creating a argument-heavy function.

How do I make my code more idiomatic?

Answer 1

My main issue with this code is the function interface as you already identified yourself. These are the most glaring issues in my opinion:

• Parameter names are not clear. Names like i and n might be good enough in very short, self-contained loops/closures, but not as function parameters. I similarly don't like abbreviations like orig, and cur because the full words are not much longer. Always consider you first see this function, is it original or origin, is it current or cursor? Your interface should be clear without reading the code.
• You are always passing a full string slice while you know you will only read from a certain offset (i).
• Passing n is redundant, as almost any check that you do against this can be replaced by checking if you reached the end of orig.
• Similarly but less obvious passing i is redundant. The obvious part is related to the first point, if you only pass the slice this represents offset 0. Now, you also use this as a cache key, but that's not necessary. If instead of passing the full slice you only push the 'remaining' string you can use this as cache key to exactly the same effect.
• You insert true in the cache, which requires it to be a map, but there are several reasons why this is useless. I'd just use a HashSet that is only updated for false. Reasons are as follows:
  • If you found a 'true', the function finished anyway.
  • When indexed by usize and with this judging system you can't use the cache for multiple string inputs (and never for multiple word inputs). So the true cache is even useless here.
  • But even if you could re-use the cache, the true adds little, because you can quickly prune the false branches already.
• You explicitly end with return false;, it is more idiomatic to simply say false (without the semicolon).
• You have a whole construct that basically loops over a splitted version of your input. This can be significantly simplified by using the built-in split_at.

Based on all this I refactored your original algorithm to the following:

use std::collections::HashSet;
impl Solution {
    fn dfs(remaining: &str, words: &HashSet<String>, mut cache: &mut HashSet<String>) -> bool {
        for i in 1..remaining.len() + 1 {
            let (word, remaining) = remaining.split_at(i);
            if words.contains(word.into())
                && !cache.contains(remaining.into())
                && Self::dfs(remaining, &words, &mut cache)
            {
                return true;
            }
        }
        if remaining.len() == 0 {
            true
        } else {
            cache.insert(remaining.into());
            false
        }
    }
    pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
        let set = word_dict.into_iter().collect::<HashSet<String>>();
        let mut cache = HashSet::new();
        Self::dfs(&s.as_str(), &set, &mut cache)
    }
}

This may not yet be ideal, I for example don't like remaining and dfs as names. Other improvements you could try but are honestly overkill for a braintease exercise:

• It seems somewhat weird to pass words and cache as a parameter. More idiomatic would be to make a WordBreakChecker struct. You provide it with a new initializer that sets the cache and words, and then have a single dfs (or better check) function that only takes the string as input.
• In my example I still index the slice explicitly by using a for loop and split_at. That's good enough for here, but it may be interesting practice to implement the Iterator trait to iterate over these combinations directly (honestly, it may exist already in std or a crate, I didn't look to hard).