Word Search II algorithm in JavaScript

Question

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

Luke Woodward · Accepted Answer · 2020-11-05 20:23:59Z

3

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.

answered Nov 5, 2020 at 20:23

Luke Woodward

65.4k16 gold badges94 silver badges108 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

myTest532 myTest532 Over a year ago

Awesome! Yes, I forgot this detail. Thank you. Would you say that this code runs in O(n2) time complexity because the board loop?

Luke Woodward Over a year ago

No, I don't know the exact time complexity, but I would guess that it is O(n × 4^n), where n is the number of squares in the grid. The worst-case scenario appears to be attempting to find a word where all but the last letter are the same in a grid where all the letters are the same as the first letter of the word (e.g. trying to find aaaaaaaab in a 3 × 3 grid of as). Imagine a 10 × 10 grid, with 100 as in it, and think how long it would take your code to run when you ask it to find the word aaa.....ab, where there are 99 as.

Luke Woodward Over a year ago

@myTest532myTest532: 4^n was a guess based on the fact that from each square you head off in four different directions. However, you don't proceed any further if you fall off the grid or hit a square you've already visited, and as you get further in there are more already-visited squares in the grid. 3^n may be more accurate, as that takes into account the fact that at each square other than the first you can't go back to the previous. The truth however is I really don't know the time complexity of this algorithm!

Collectives™ on Stack Overflow

Word Search II algorithm in JavaScript

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related