LeetCode: Word Squares

Posted on August 5, 2019July 26, 2020 by braindenny

Word Squares

Similar Problems:

Given a set of words (without duplicates), find all word squares you can build from them.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 <= k < max(numRows, numColumns).

For example, the word sequence [“ball”,”area”,”lead”,”lady”] forms a word square because each word reads the same both horizontally and vertically.

b a l l
a r e a
l e a d
l a d y

Note:

There are at least 1 and at most 1000 words.
All words will have the exact same length.
Word length is at least 1 and at most 5.
Each word contains only lowercase English alphabet a-z.

Example 1:

Input:
["area","lead","wall","lady","ball"]

Output:
[
  [ "wall",
    "area",
    "lead",
    "lady"
  ],
  [ "ball",
    "area",
    "lead",
    "lady"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Example 2:

Input:
["abat","baba","atan","atal"]

Output:
[
  [ "baba",
    "abat",
    "baba",
    "atan"
  ],
  [ "baba",
    "abat",
    "baba",
    "atal"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Github: code.dennyzhang.com

Credits To: leetcode.com

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

Solution:

// https://code.dennyzhang.com/word-squares
// Basic Ideas: trie + backtracking
//
//   a r e a
//   r
//   e
//   a
//
// Notice: could one word be used more than one time?
//
// Complexity: Time O(n^2) Space O(n^2)
type Trie struct {
    children map[byte]*Trie
    startIndices map[int]bool
}

func startsWith(root *Trie, prefix []byte) []int {
    p := root
    for _, ch := range prefix {
        if _, ok := p.children[ch]; !ok {
            return []int{}
        }
        p = p.children[ch]
    }
    res := []int{}
    for index, _ := range p.startIndices {
        res = append(res, index)
    }
    return res
}

func dfs(pos int, l []string, words []string, root *Trie, res *[][]string) {
    if pos == len(words[0]) {
        // get result
        l2 := make([]string, len(l))
        copy(l2, l)
        *res = append(*res, l2)
        return
    }
    prefix := make([]byte, len(l))
    for i:=0; i<len(l); i++ {
        prefix[i] = l[i][len(l)]
    }
    indices := []int{}
    if len(prefix) == 0 {
        for index, _ := range root.startIndices {
            indices = append(indices, index)
        }
    } else {
        indices = startsWith(root, prefix)
    }
    for _, index := range indices {
        l = append(l, words[index])
        dfs(pos+1, l, words, root, res)
        l = l[0:len(l)-1]
    }
}

func wordSquares(words []string) [][]string {
    // build a trie tree
    root := &Trie{startIndices:map[int]bool{}, children:map[byte]*Trie{}}
    for index, word := range words {
        p := root
        for i, _ := range word {
            ch := word[i]
            p.startIndices[index] = true
            if _, ok := p.children[ch]; !ok {
                q := &Trie{startIndices:map[int]bool{}, children:map[byte]*Trie{}}
                p.children[ch] = q
            }
            p = p.children[ch]
        }
    }
    // backtracking
    res := [][]string{}
    dfs(0, []string{}, words, root, &res)
    return res
}

Post Views: 0