Word Squares

HardBacktrackingtrie

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A **word square** is a list of L words, each of length L, arranged as rows so that the r-th row reads the same as the r-th column for every r. In other words, square[r][c] == square[c][r] for all r, c. Given an array words of **distinct** strings that all have the same length, return every word square that can be formed from them. The same word may appear in more than one row of a square. Each square is a list of words in row order, and that order matters. The squares themselves may be returned in **any order**. Return [] if no square exists.

Examples

Input: words = ["area","lead","wall","lady","ball"]
Output: [["ball","area","lead","lady"],["wall","area","lead","lady"]]
Reading down the columns of either square gives the same four words as reading across the rows.
Input: words = ["abat","baba","atan","atal"]
Output: [["baba","abat","baba","atal"],["baba","abat","baba","atan"]]
`baba` is used twice in each square, which is allowed.

Constraints

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 5
  • All words have the same length
  • Words consist of lowercase English letters and are distinct

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More trie problems