CODEWITHSUNDEEP
javascriptarraysdepth-first-search
myTest532 myTest532
myTest532 myTest532

Reputation: 2381

Word Search II algorithm in JavaScript

I'm trying to creating my own solution for the Word Search II problem (please do not sent me links with someone's else solution, I'm trying to understand what is wrong in my code).

Problem: Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

My solution:

var findWords = function(board, words) {
    
    let output = new Set();
    const initials = new Map();
    for(let i=0; i<words.length; i++) {
        let temp;
        if(initials.has(words[i][0]))
            temp = initials.get(words[i][0]);
        else
            temp = [];
        temp.push(words[i]);
        initials.set(words[i][0], temp);
    }
    
    const checkOrder = (row, col, word, tempWord, visited) => {
        if(row < 0 || row >= board.length || col < 0 || col >= board[row].length || board[row][col] !== word[tempWord.length])
            return;
        if(visited[row][col] === 1) return;
        
        tempWord += board[row][col];
        visited[row][col] = 1;
        if(tempWord === word)   output.add(word);            
        
        checkOrder(row, col+1, word, tempWord, visited);
        checkOrder(row, col-1, word, tempWord, visited);
        checkOrder(row+1, col, word, tempWord, visited);
        checkOrder(row-1, col, word, tempWord, visited);
    }
    
    for(let i=0; i<board.length; i++) {
        for(let j=0; j<board[i].length; j++) {
            if(initials.has(board[i][j])) {
                // might form a word
                const listWords = initials.get(board[i][j]);
                for(let k=0; k<listWords.length; k++) {
                    const visited = new Array(board.length).fill(0).map(() => new Array(board[0].length).fill(0));
                    const word = listWords[k];
                    checkOrder(i, j, word, "", visited);
                }
            }
        }
    }
    
    return Array.from(output);
};

It works just fine for the input above. However for the input below:

board: [["a","b","c"],["a","e","d"],["a","f","g"]]
words: ["abcdefg","gfedcbaaa","eaabcdgfa","befa","dgc","ade"]

My output is: ["abcdefg","befa","gfedcbaaa"] Why my code is not counting the work: "eaabcdgfa"?

Thank you

Upvotes: 0

Views: 1265

Answers (1)

Luke Woodward
Luke Woodward

Reputation: 64949

When searching for the word eaabcdgfa in your second board, your depth-first search algorithm:

  • starts at the e in the centre, marks it as visited,
  • finds an a in the centre-left, marks it as visited,
  • finds an a in the bottom-left, marks it as visited,
  • doesn't find a b next to the a in the bottom-left, so backtracks to the first a,
  • finds another a in the top-left, marks it as visited,
  • finds b, c, d, g and f around the edge of the board, marking them all as visited,
  • is unable to add the a in the bottom left because it has been marked as visited.

The problem is that the a in the bottom-left was marked as visited despite it not being part of the route traced from the e at the centre to the f at the bottom-centre.

If you want the visited array to record the grid squares that have been visited by the current stack of recursive calls to checkOrder, then you need to mark grid squares as no longer visited before checkOrder ends. You can do this by adding the line

        visited[row][col] = 0;

to the bottom of your checkOrder function, below all the recursive calls to checkOrder.

I made this change to your code and it found the word eaabcdfga.

Upvotes: 3

Related Questions