Quick Overview

This question evaluates algorithm design for efficient multi-word search in a character grid, testing competencies in constrained graph traversal, managing large dictionaries, and selecting data structures for efficient lookup.

Find Words in a Character Grid

Company: ByteDance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement `findWords(board, words)` for a word-search game. You are given an `m x n` grid of lowercase English letters and a list of lowercase dictionary words. A word can be formed by starting at any cell and repeatedly moving one step up, down, left, or right. The same grid cell may not be used more than once in a single word. Return all unique dictionary words that can be formed in the grid. The output order does not matter. Constraints: - `1 <= m, n <= 12` - `1 <= words.length <= 30000` - `1 <= words[i].length <= 10` - All words contain only lowercase English letters. Optimize for a large dictionary and avoid searching the grid independently for every word.

Overview: This question evaluates algorithm design for efficient multi-word search in a character grid, testing competencies in constrained graph traversal, managing large dictionaries, and selecting data structures for efficient lookup.

Read the full ByteDance Software Engineer interview experience this question came from

Implement `solution(board, words)` for a word-search game. You are given an `m x n` grid of lowercase English letters and a list of lowercase dictionary words. A word can be formed by starting at any cell and repeatedly moving one step up, down, left, or right. The same grid cell may not be used more than once in a single word. Return all unique dictionary words that can be formed in the grid. Because the dictionary can be large, your solution should avoid searching the board independently for every word. For deterministic output in this problem, return the result sorted in lexicographical order.

Constraints

  • 1 <= len(board), len(board[0]) <= 12
  • 1 <= len(words) <= 30000
  • 1 <= len(words[i]) <= 10
  • All board cells and words contain only lowercase English letters

Examples

Input: ([['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']], ['oath','pea','eat','rain'])

Expected Output: ['eat', 'oath']

Explanation: The words 'oath' and 'eat' can be formed by valid adjacent paths. 'pea' and 'rain' cannot.

Input: ([['a']], ['a','aa','b','a'])

Expected Output: ['a']

Explanation: Only 'a' can be formed. 'aa' would require reusing the same cell, and duplicates should appear only once in the result.

Hints

  1. Searching the full grid separately for every word repeats a lot of work. Think about a data structure that groups words by shared prefixes.
  2. While doing DFS from the board, stop exploring as soon as the current path is not a prefix of any remaining dictionary word.

Loading coding console...