Word Search II LeetCode Solution

/ Leetcode Solution / Airbnb, Backtracking, Google, Hard, LeetCode Solution, Microsoft, Tree

Last updated on October 10th, 2024 at 12:50 am

Here, We see Word Search II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Topics

Backtracking, Tree

Companies

Airbnb, Google, Microsoft

Level of Question

Hard

Word Search II LeetCode Solution

Word Search II LeetCode Solution

Problem Statement

Given an m x n board of characters and a list of strings words, return all words on the board.

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

Word Search II leetcode search1
fig-1
Example 1: (fig-1)
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"]
Word Search II leetcode search2
fig-2
Example 2: (fig-2)
Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

1. Word Search II Leetcode Solution C++

class Solution {
    struct TrieNode {
        TrieNode *children[26];
        string word;

        TrieNode() : word("") {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
        }
    };
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieNode *root = buildTrie(words);
        vector<string> result;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                dfs(board, i, j, root, result);
            }
        }
        return result;
    }

    TrieNode *buildTrie(vector<string> &words) {
        TrieNode *root = new TrieNode();
        for (int j = 0; j < words.size(); j++) {
            string word = words[j];
            TrieNode *curr = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word[i] - 'a';
                if (curr->children[c] == nullptr) {
                    curr->children[c] = new TrieNode();
                }
                curr = curr->children[c];
            }
            curr->word = word;
        }
        return root;
    }

    void dfs(vector<vector<char>> &board, int i, int j, TrieNode *p, vector<string> &result) {
        char c = board[i][j];
        if (c == '#' || !p->children[c - 'a']) return;
        p = p->children[c - 'a'];
        if (p->word.size() > 0) {
            result.push_back(p->word);
            p->word = "";
        }

        board[i][j] = '#';
        if (i > 0) dfs(board, i - 1, j, p, result);
        if (j > 0) dfs(board, i, j - 1, p, result);
        if (i < board.size() - 1) dfs(board, i + 1, j, p, result);
        if (j < board[0].size() - 1) dfs(board, i, j + 1, p, result);
        board[i][j] = c;
    }
};

1.1 Explanation

  1. TrieNode Structure:
    • TrieNode is a nested structure within Solution that holds an array children of TrieNode pointers, one for each possible lowercase English letter (‘a’ to ‘z’). Each node also stores a word which is the word ending at that node.
  2. Building the Trie (buildTrie):
    • This function constructs a Trie from a list of words. For each word, it starts at the root and traverses down, creating new nodes as necessary for each character in the word. The final node of each word (curr->word) is marked with the word itself.
  3. Depth-First Search (dfs):
    • This function explores the board starting from each cell. It checks if the current character exists as a child in the Trie (p->children[c – ‘a’]). If not, or if the character has already been visited (‘#’), it returns.
    • If a word ends at the current node (!p->word.empty()), it adds that word to the result vector (result) and clears the word to prevent duplicate results.
    • It marks the current board cell as visited (board[i][j] = ‘#’), explores neighboring cells recursively (up, down, left, right), and then restores the original character after exploration (board[i][j] = c).

1.2 Time Complexity

  • Trie Construction: O(L) where L is the total length of all words combined.
  • DFS Traversal: O(m * n * 4L), where m is the number of rows, n is the number of columns in the board, and L is the maximum length of words.

1.3 Space Complexity

  • Trie Structure: O(26 * L * N), where L is the average length of words and N is the number of words. Each TrieNode has 26 children pointers and may store up to L characters.
  • DFS Stack: O(m * n) for recursion depth.

2. Word Search II Leetcode Solution Java

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
    TrieNode root = buildTrie(words);
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs (board, i, j, root, res);
        }
    }
    return res;
}

public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
    char c = board[i][j];
    if (c == '#' || p.next[c - 'a'] == null) return;
    p = p.next[c - 'a'];
    if (p.word != null) {   // found one
        res.add(p.word);
        p.word = null;     // de-duplicate
    }

    board[i][j] = '#';
    if (i > 0) dfs(board, i - 1, j ,p, res); 
    if (j > 0) dfs(board, i, j - 1, p, res);
    if (i < board.length - 1) dfs(board, i + 1, j, p, res); 
    if (j < board[0].length - 1) dfs(board, i, j + 1, p, res); 
    board[i][j] = c;
}

public TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {
        TrieNode p = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (p.next[i] == null) p.next[i] = new TrieNode();
            p = p.next[i];
       }
       p.word = w;
    }
    return root;
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    String word;
    }
}

2.1 Explanation

  1. TrieNode Class:
    • TrieNode class represents each node in the Trie. It has an array next of size 26 (for ‘a’ to ‘z’) to store child nodes and a word string to store the word ending at that node.
  2. buildTrie Method:
    • buildTrie constructs the Trie from the array of words. It iterates through each word, and for each character in the word, it checks if the corresponding child node exists. If not, it creates a new TrieNode and moves to that node.
  3. dfs Method:
    • dfs (Depth-First Search) is used to explore the board starting from each cell. It checks if the current character (board[i][j]) is in the Trie (p.next[c – ‘a’]). If not, or if the cell has been visited (‘#’), it returns.
    • If a valid word is found (p.word != null), it adds the word to the result list (res) and removes the word from the Trie to avoid duplicates (p.word = null).
    • It marks the current board cell as visited (board[i][j] = ‘#’), recursively explores neighboring cells (up, down, left, right), and then restores the original character after exploration.
  4. findWords Method:
    • findWords initializes an empty result list (res), builds the Trie using buildTrie, and then iterates through each cell in the board, calling dfs to find words starting from that cell.

2.2 Time Complexity

  • Trie Construction: O(L), where L is the total length of all words combined.
  • DFS Traversal: O(m * n * 4L), where m is the number of rows, n is the number of columns in the board, and L is the maximum length of words.

2.3 Space Complexity

  • Trie Structure: O(26 * L * N), where L is the average length of words and N is the number of words. Each TrieNode has 26 children and may store up to L characters.
  • DFS Stack: O(m * n) for recursion depth.

3. Word Search II Leetcode Solution JavaScript

var findWords = function(board, words) {
    const res = [], trie = {};
  
  for (let word of words) {
    let curNode = trie;
    for (let char of word) {
      curNode[char] = curNode[char] || {};
      curNode[char].count = curNode[char].count + 1 || 1;
      curNode = curNode[char];
    };
    curNode.end = word;
  }
  
  for (let row = 0; row < board.length; row++) {
    for (let col = 0; col < board[row].length; col++) {
      if (trie[board[row][col]]) traverse(row, col);
    }
  }  
  return res;
  
  function traverse(row, col, node = trie) {
    if (!board[row][col]) return;
    
    const char = board[row][col], curNode = node[char];
    if (!curNode) return;
    
    if (curNode.end) {
      res.push(curNode.end);
      let toDelete = trie;
      for (let char of curNode.end) {
        toDelete[char].count--;
        if (!toDelete[char].count) {
          delete(toDelete[char]);
          break;
        }
        toDelete = toDelete[char];
      }
      curNode.end = null;
    }
    
    board[row][col] = 0;
    (col - 1 >= 0) && traverse(row, col - 1, curNode);
    (col + 1 < board[row].length) && traverse(row, col + 1, curNode);
    (row - 1 >= 0) && traverse(row - 1, col, curNode);
    (row + 1 < board.length) && traverse(row + 1, col, curNode);
    board[row][col] = char;
  }
};

3.1 Explanation

  1. Trie Construction:
    • The function begins by initializing an empty result array res and an empty Trie trie.
    • It iterates through each word in the words array and constructs the Trie using nested objects (trie).
  2. DFS Traversal (traverse Function):
    • It then iterates through each cell of the board and calls a recursive DFS function traverse to search for words starting from each cell.
    • traverse checks if the current character on the board exists in the Trie (node[char]). If not, it returns.
    • If a valid word (curNode.end) is found, it adds it to the res array and removes it from the Trie to avoid duplicates.
    • It marks the current board cell as visited (board[row][col] = 0), recursively explores neighboring cells (left, right, up, down), and then restores the original character after exploration.
  3. Edge Cases:
    • It handles cases where the cell is out of bounds (!board[row][col]) and ensures efficient exploration by marking visited cells (board[row][col] = 0).

3.2 Time Complexity

  • Trie Construction: O(L), where L is the total length of all words combined.
  • DFS Traversal: O(m * n * 4L), where m is the number of rows, n is the number of columns in the board, and L is the maximum length of words.

3.3 Space Complexity

  • Trie Structure: O(26 * L * N), where L is the average length of words and N is the number of words. Each Trie node potentially stores up to 26 children.
  • DFS Stack: O(m * n), for recursion depth.

4. Word Search II Leetcode Solution Python

class Solution(object):
    def findWords(self, board, words):
        m, n = len(board), len(board[0])
        dic = defaultdict(set)
    
        for i in range(m):
            for j in range(n):
                dic[board[i][j]].add((i, j))
        results = deque()
    
        word, lngth, word_isReversed = '', 0, False
        def dfs(cord, indx):
            if indx == lngth: 
                if word_isReversed:
                    results.append(word[::-1])
                else:
                    results.append(word)
                return True
        
            ch = word[indx]
            i, j = cord
            for cand in [(i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j)]:
                if cand in dic[ch]:
                    dic[ch].remove(cand)
                    flag = dfs(cand, indx + 1)
                    dic[ch].add(cand)
                    if flag: return True
            return False

        ref = set()
        for i in range(m):
            for j in range(n - 1):
                ref.add(board[i][j] + board[i][j + 1])
        for j in range(n):
            for i in range(m - 1):
                ref.add(board[i][j] + board[i + 1][j])
                
        def check(word):
            for i in range(len(word) - 1):
                if word[i] + word[i + 1] not in ref:
                    if word[i + 1] + word[i] not in ref:
                        return False

            return True
    
        for w in words:
            if check(w):
                if w[:4] == w[0]*4 or len(dic[w[-1]]) < len(dic[w[0]]):
                    word = w[::-1]
                    word_isReversed = True
                else:
                    word = w
                    if word_isReversed: word_isReversed = False
    
                lngth = len(word)
                for cord in list(dic[word[0]]):
                    dic[word[0]].remove(cord)
                    flag = dfs(cord, 1)
                    dic[word[0]].add(cord)
                    if flag: break
        return results

4.1 Explanation

  1. Initialization:
    • m, n represent the dimensions of the board (m rows and n columns).
    • dic is a defaultdict of sets where each character on the board maps to a set of coordinates (i, j) where it appears.
  2. DFS Function (dfs):
    • Recursively searches for a word starting from a given position (cord) and index (indx) in the word.
    • Checks neighboring cells (up, down, left, right) to find the next character of the word.
    • Uses backtracking (dic[ch].remove(cand) and dic[ch].add(cand)) to mark positions as visited and restore them after exploration.
  3. Validation (check Function):
    • Ensures that adjacent characters in the word exist as adjacent characters on the board (ref set).
  4. Main Logic:
    • Iterates through each word in words and checks if it can potentially exist on the board (check function).
    • Determines the direction (normal or reversed) based on conditions (w[:4] == w[0]*4 or length of occurrences in dic).
    • Initiates DFS from each valid starting position of the word.
  5. Output:
    • Appends found words to results using a deque for efficient appending and popping.

4.2 Time Complexity

  • Trie Construction: O(m * n), where m is the number of rows and n is the number of columns in the board.
  • DFS Traversal: O(4L), where L is the length of the longest word. In the worst case, each cell might explore four directions.

4.3 Space Complexity

  • Trie Structure: O(m * n) for storing board positions in dic and ref.
  • DFS Stack: O(L) for recursion depth, where L is the length of the longest word.

Related Posts

Scroll to Top