LeetCode: Word Search II – Prepare For Coder Interview

Word Search II

Similar Problems:

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.

For example,

Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
Return ["eat","oath"].

Note:
You may assume that all inputs are consist of lowercase letters a-z.

You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?

If the current candidate does not exist in all words' prefix, you
could stop backtracking immediately. What kind of data structure could
answer such query efficiently? Does a hash table work? Why or why not?
How about a Trie? If you would like to learn how to implement a basic
trie, please work on this problem: Implement Trie (Prefix Tree) first.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: trie + dfs

// https://code.dennyzhang.com/word-search-ii
// Basic Ideas: Trie + Graph
//
//  For each position in the graph, do a trie lookup
//
// Complexity: Time ?, Space ?
type Trie struct {
    children [26]*Trie
    isLeaf bool
    index int
}

func dfs(i int, j int, root *Trie, board [][]byte, seen []bool) {
    if i<0 || i>=len(board) || j<0 || j>=len(board[0]) {
        return
    }

    if board[i][j] == '#' {
        // already visited
        return
    }
    b := int(board[i][j]-'a')
    p := root.children[b]
    if p == nil {
        // no match
        return
    }
    if p.isLeaf {
        // Can't use root.isLeaf, since we won't hit an empty character
        seen[p.index] = true
        // Don't return, strings in words array can be prefix strings
    }   
    board[i][j] = '#'
    dfs(i+1, j, p, board, seen)
    dfs(i-1, j, p, board, seen)
    dfs(i, j+1, p, board, seen)
    dfs(i, j-1, p, board, seen)
    // backtrack
    board[i][j] = byte(b+'a')
}

func findWords(board [][]byte, words []string) []string {
    // build a trie from words
    root := &Trie{}
    for i, w := range words {
        p := root
        for _, ch := range w {
            b := byte(ch)-'a'
            if p.children[b] == nil {
                p.children[b] = &Trie{}
            }
            p = p.children[b]
        }
        p.isLeaf = true
        p.index = i
    }
    seen := make([]bool, len(words))
    for i, row := range board {
        for j, _ := range row {
            dfs(i, j, root, board, seen)
        }
    }
    // fmt.Println(seen)
    res := []string{}
    for i, b := range seen {
        if b {
            res = append(res, words[i])
        }
    }
    // assume the order of the result doesn't matter
    return res
}

Solution: trie with extra datastructure + no hashmap to avoid duplicates + use [26] instead of hashmap in trie

// https://code.dennyzhang.com/word-search-ii
// Basic Ideas: trie
//
// Notice: avoid duplicate entries
// Assumption: the order doesn't matter
//
// Complexity: Time O(n*m*w), Space O(w)
type Trie struct {
    children [26]*Trie
    isLeaf bool
    index int
}

func dfs(i int, j int, board [][]byte, p *Trie, seen []bool) {
    // return if invalid position or visited
    if i<0 || i>=len(board) || j<0 || j>=len(board[0]) || board[i][j] == '#' {
        return
    }

    ch := board[i][j]
    q := p.children[ch-'a']
    // abort, if not found in trie
    if q == nil {
        return
    }

    // get a candidate, and not a duplicate one
    if q.isLeaf && !seen[q.index] {
        seen[q.index] = true
    }
    // dfs
    for _, offset := range [][]int{[]int{1, 0}, []int{-1, 0}, []int{0, 1}, []int{0, -1}} {
        board[i][j] = '#'
        dfs(i+offset[0], j+offset[1], board, q, seen)
        // backtracking
        board[i][j] = ch
    }
}

func findWords(board [][]byte, words []string) []string {
    if len(board) == 0 || len(board[0]) == 0 || len(words) == 0 {
        return []string{}
    }

    root := &Trie{}
    // build trie
    for index, word := range words {
        p := root
        for i, _ := range word {
            j := word[i]-'a'
            if p.children[j] == nil {
                p.children[j] = &Trie{}
            }
            p = p.children[j]
        }
        p.isLeaf = true
        p.index = index
    }
    seen := make([]bool, len(words))
    for i, row := range board {
        for j, _ := range row {
            dfs(i, j, board, root, seen)
        }
    }
    res := []string{}
    for i, b := range seen {
        if b {
            res = append(res, words[i])
        }
    }
    return res
}

Solution: trie + without hashmap of state

// https://code.dennyzhang.com/word-search-ii
// Basic Ideas: trie
//
// Notice: avoid duplicate entries
// Assumption: the order doesn't matter
//
// Complexity: Time O(n*m*w), Space O(w)
type Trie struct {
    children map[byte]*Trie
    isLeaf bool
}

func dfs(i int, j int, combination []byte, board [][]byte, p *Trie, m map[string]bool) {
    // return if invalid position or visited
    if i<0 || i>=len(board) || j<0 || j>=len(board[0]) || board[i][j] == '#' {
        return
    }

    ch := board[i][j]
    q := p.children[ch]
    // abort, if not found in trie
    if q == nil {
        return
    }

    // get a candidate
    if q.isLeaf {
        m[string(append(combination, ch))] = true
    }
    // dfs
    for _, offset := range [][]int{[]int{1, 0}, []int{-1, 0}, []int{0, 1}, []int{0, -1}} {
        combination = append(combination, ch)
        board[i][j] = '#'
        dfs(i+offset[0], j+offset[1], combination, board, q, m)
        // backtracking
        board[i][j] = ch
        combination = combination[0:len(combination)-1]
    }
}

func findWords(board [][]byte, words []string) []string {
    if len(board) == 0 || len(board[0]) == 0 || len(words) == 0 {
        return []string{}
    }

    root := &Trie{children:map[byte]*Trie{}}
    // build trie
    for _, word := range words {
        p := root
        for i, _ := range word {
            ch := word[i]
            if _, ok := p.children[ch]; !ok {
                p.children[ch] = &Trie{children:map[byte]*Trie{}}
            }
            p = p.children[ch]
        }
        p.isLeaf = true
    }
    m := map[string]bool{}
    for i, row := range board {
        for j, _ := range row {
            dfs(i, j, []byte{}, board, root, m)
        }
    }
    res := []string{}
    for k, _ := range m {
        res = append(res, k)
    }
    return res
}

Solution: trie + hashmap as state of each cell

// https://code.dennyzhang.com/word-search-ii
// Basic Ideas: trie
//
// Notice: avoid duplicate entries
// Assumption: the order doesn't matter
//
// Complexity: Time O(n*m*w), Space O(w)
type Trie struct {
    children map[byte]*Trie
    isLeaf bool
}

func dfs(i int, j int, combination []byte, board [][]byte, visited [][]bool, p *Trie, m map[string]bool) {
    // return if invalid position or visited
    if i<0 || i>=len(board) || j<0 || j>=len(board[0]) || visited[i][j] {
        return
    }

    ch := board[i][j]
    q := p.children[ch]
    // abort, if not found in trie
    if q == nil {
        return
    }

    // get a candidate
    if q.isLeaf {
        m[string(append(combination, ch))] = true
    }

    // dfs
    for _, offset := range [][]int{[]int{1, 0}, []int{-1, 0}, []int{0, 1}, []int{0, -1}} {
        visited[i][j] = true
        combination = append(combination, ch)
        dfs(i+offset[0], j+offset[1], combination, board, visited, q, m)
        // backtracking
        combination = combination[0:len(combination)-1]
        visited[i][j] = false
    }
}

func findWords(board [][]byte, words []string) []string {
    if len(board) == 0 || len(board[0]) == 0 || len(words) == 0 {
        return []string{}
    }

    root := &Trie{children:map[byte]*Trie{}}
    // build trie
    for _, word := range words {
        p := root
        for i, _ := range word {
            ch := word[i]
            if _, ok := p.children[ch]; !ok {
                p.children[ch] = &Trie{children:map[byte]*Trie{}}
            }
            p = p.children[ch]
        }
        p.isLeaf = true
    }
    m := map[string]bool{}
    for i, row := range board {
        for j, _ := range row {
            visited := make([][]bool, len(board))
            for k, _ := range visited {
                visited[k] = make([]bool, len(board[0]))
            }
            dfs(i, j, []byte{}, board, visited, root, m)
        }
    }
    res := []string{}
    for k, _ := range m {
        res = append(res, k)
    }
    return res
}

Post Views: 10