Largest crossword matrix


  • 0
    G

    Given a large matrix of letters and a large dictionary of words, return the largest area matrix from (0, 0) to (i, j) where every row and column spell a valid word.

    For example, given the matrix below,

    [ ["R", "I", "B", "B"],
      ["Y", "O", "U", "C"],
      ["E", "N", "D", "A"],
      ["T", "H", "E", "Y"]
    ]
    

    The resulting matrix is below because every row and column spell out a word ("RIB", "YOU", "END", "RYE", "ION", "BUD").

    [ ["R", "I", "B"],
      ["Y", "O", "U"],
      ["E", "N", "D"]
    ]
    

  • 0
    L

    @gangstamuffin said in Largest crossword matrix:

    Given a large matrix of letters and a large dictionary of words, return the largest area matrix from (0, 0) to (i, j) where every row and column spell a valid word.
    For example, given the matrix below,
    [ ["R", "I", "B", "B"],
    ["Y", "O", "U", "C"],
    ["E", "N", "D", "A"],
    ["T", "H", "E", "Y"]
    ]

    The resulting matrix is below because every row and column spell out a word ("RIB", "YOU", "END", "RYE", "ION", "BUD").
    [ ["R", "I", "B"],
    ["Y", "O", "U"],
    ["E", "N", "D"]
    ]

    Since every row and colum spells a valid word, each word is of the same length. I can think of the following algorithm to solve it.

    1. Make a trie with the given dictionary
    2. start from (0,0) till you find a word.
      • try validating the rows and cols
      • move to the next index
    3. Find a larger word.

    So essentially,
    'R'->'I'->'B' , check the 3x matrix and validate that.
    ignore anything of size <3. We may actually stop at this point because the dimension of the matrix won't allow for more than size 3
    3.

    Does anyone have a better idea?


Log in to reply
 

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