JS Solution


  • 0
    S

    The idea behind this problem is actually relatively simple. You would first build out a trie that would contain all the words.

    You would then begin by setting up a for of loop for all the words, trying each of them as the top word of word squares.

    Once you have the top word in a square, you check whether or not the character at index after the first letter forms a word, if it does, you add that word to the square.

    Now you have two words in a square, and u look at whether the second from front character from each one of them is a prefix to a word in your trie. If so you add that word to the square as well.

    You keep doing that and once you get to a point where the number of words in your square is equal to the length of the first word in the square you know you have a perfect word sqaure.

    Why do you check the prefixes in the way that you do? Because of the mirror format of a word sqaure if you draw a diagonal through it from top left to bottom right.

    class TrieNode {
      constructor() {
        this.children = {};
        this.isWord = false;
      }
    }
    
    class WordSquares {
      constructor() {
        this.root = new TrieNode();
      }
    
      wordSquares(words) {
        let root = this.buildTrie(words);
        let squares = [];
    
        for (let word of words) {
          let square = [];
          square.push(word);
          this.wordSquaresLong(root, word.length, square, squares);
        }
        return squares;
      }
    
      buildTrie(words) {
        let root = this.root;
    
        for (let word of words) {
          let current = root;
            
          for (let char of word) {
            if (!current.children.hasOwnProperty(char)) {
              current.children[char] = new TrieNode();
            }
            current = current.children[char];
          }
          current.isWord = true;
        }
        return root;
      }
    
      search(root, prefix) {
        let current = root;
        for (let char of prefix) {
          if (!current.children.hasOwnProperty(char)) {
            return null;
          }
          current = current.children[char];
        }
        return current;
      }
    
      wordSquaresLong(root, len, square, squares) {
        if (square.length === len) {
          squares.push(square.slice());
          return;
        }
        let prefix = this.getPrefix(square, square.length);
        let node = this.search(root, prefix);
        if (!node) {
          return;
        }
    
        let children = [];
        this.getChildren(node, prefix, children);
    
        for (let child of children) {
          square.push(child);
          this.wordSquaresLong(root, len, square, squares);
          square.splice(square.length - 1, 1);
        }
      }
    
      getPrefix(square, index) {
        let prefix = '';
        for (let i = 0; i < index; i++) {
          prefix += square[i][index];
        }
        return prefix;
      }
    
      getChildren(node, str, children) {
        if (node.isWord) {
          children.push(str);
          return;
        }
    
        for (let child of Object.keys(node.children)) {
          this.getChildren(node.children[child], str + child, children);
        }
      }
    }
    
    
    /**
     * @param {string[]} words
     * @return {string[][]}
     */
    var wordSquares = function(words) {
        let wordSquaresClass = new WordSquares();
        return wordSquaresClass.wordSquares(words);
    };
    
    wordSquares(['ball', 'lady', 'lead', 'area']);
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.