LeetCode 1066. Campus Bikes II

Problem Statement

DFS with memorization.

use std::collections::HashMap;
use std::cmp;

impl Solution {
    fn dist(worker: &Vec<i32>, bike: &Vec<i32>) -> usize {
        return ((worker[0] - bike[0]).abs() + (worker[1] - bike[1]).abs()) as usize;
    }

    fn dfs(workers: &mut Vec<Vec<i32>>, bikes: &mut Vec<Vec<i32>>, index: usize, used: usize,
           memo: &mut HashMap<String, usize>) -> usize {
        if index == workers.len() {
            return 0;
        }

        let key = [index.to_string(), String::from("."), used.to_string()].concat();
        if memo.contains_key(&key) {
            return memo.get(&key).unwrap().clone();
        }
        let mut min_dist = std::usize::MAX;
        let mut next_used = used;
        for i in 0..bikes.len() {
            if next_used & (1 << i) != 0 {
                continue;
            }
            next_used = used | (1 << i);
            min_dist = cmp::min(min_dist,
                                Self::dfs(workers, bikes, index + 1, next_used, memo) + Self::dist(&workers[index], &bikes[i]));
            next_used ^= 1 << i;
        }
        memo.insert(key, min_dist);
        return min_dist;
    }

    pub fn assign_bikes(workers: Vec<Vec<i32>>, bikes: Vec<Vec<i32>>) -> i32 {
        let mut memo = HashMap::new();
        let (mut w, mut b) = (workers.clone(), bikes.clone());
        return Self::dfs(&mut w, &mut b, 0, 0, &mut memo) as i32;
    }
}