Why is vector been modified during iteration?

I'm doing an algorithm exercise in Rust and find a strange behavior, the vector directions has four elements before iteration, but during iteration, it has two more element come out, it seems it's same from previous recursive call, but I don't understand how they are mixed together?

use std::collections::HashMap;
struct Solution {}

impl Solution {
    pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
        let mut marked = HashMap::new();
        for i in 0..board.len(){
            for j in 0..board[i].len(){
                if board[i][j] == word.chars().nth(0).unwrap(){
                     marked.insert((i,j), true);
                     return Self::dfs(&mut marked, &board, &word, 1, i, j)
                }
                marked.remove(&(i,j));
            }
        }
        return false
    }
       

    fn dfs(marked: &mut HashMap<(usize, usize), bool>, board: &Vec<Vec<char>>, word:&String, index:usize, i:usize, j:usize) -> bool {
        if index == word.len() {
            return true
        }

        let mut found = false;
        let mut directions = Vec::new();
        if i > 0 {
            directions.push((i-1, j))
        }
        if i < board.len()-1 {
            directions.push((i+1, j))
        }
        if j > 0 {
             directions.push((i, j-1))
        }
        if j < board[i].len()-1 {
            directions.push((i, j+1))
        }
        println!("index: {index}, directions: {:?}", directions);
        for direction in directions {
            println!(" curr direction: {:?}", direction);
            let (i,j) = direction;
           
            if marked.contains_key(&(i,j)) {
                continue
            }
            marked.insert((i,j), true);
            if board[i][j] == word.chars().nth(index).unwrap() {
                found =  Self::dfs(marked, board, word, index+1, i, j)
            }
             marked.remove(&(i,j));
            if found {
                return true
            }
        }
        return false
    }
}

fn main(){
    let board = [['C','A','A'].to_vec(),['A','A','A'].to_vec(),['B','C','D'].to_vec()].to_vec();
    let word = "AAB".to_string();
    println!("ans: {}", Solution::exist(board, word));
    
}

(Playground)

Output:

index: 1, directions: [(1, 1), (0, 0), (0, 2)]
 curr direction: (1, 1)
index: 2, directions: [(0, 1), (2, 1), (1, 0), (1, 2)]
 curr direction: (0, 1)
 curr direction: (2, 1)
 curr direction: (1, 0)
 curr direction: (1, 2)
 curr direction: (0, 0)
 curr direction: (0, 2)
index: 2, directions: [(1, 2), (0, 1)]
 curr direction: (1, 2)
 curr direction: (0, 1)
ans: false

The vector is not being modified, you're just confusing the prints from one function call with a recursive one. If you print some markers before starting a recursive call and after it returns you should see something like this:

index: 1, directions: [(1, 1), (0, 0), (0, 2)]
 curr direction: (1, 1)
 {
    index: 2, directions: [(0, 1), (2, 1), (1, 0), (1, 2)]
     curr direction: (0, 1)
     curr direction: (2, 1)
     curr direction: (1, 0)
     curr direction: (1, 2)
 }
 curr direction: (0, 0)
 curr direction: (0, 2)
 {
    index: 2, directions: [(1, 2), (0, 1)]
     curr direction: (1, 2)
     curr direction: (0, 1)
 }
ans: false

As you can see the two additional directions didn't come from the vector with 4 elements, instead they were the ones from the first vector that weren't executed yet.

2 Likes

ah, thanks a lot~

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.