How to solve this interesting string problem ?

Revision en3, by yamih23436, 2021-06-08 07:43:27

Saw this problem in a Leetcode discussion : https://leetcode.com/discuss/interview-experience/1257566/goldman-sachs-tech-analyst-bengaluru-2021-off-campus-offer

Given 2N words each of length N. We have to arrange all the words in a matrix of size N * N such that all the words can be read in the crossword matrix (horizontally/vertically). Also, find the lexicographically smallest arrangement if many are possible: Not sure about constraints , but is there any better way other than brute force ?

Example:

Input:

N = 3

{abc, bfg, cgk, ade, dfg, ejk}

Output:

abc

dfg

ejk

Tags #strings, #matrix

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English yamih23436 2021-06-09 12:18:01 3 Tiny change: 'oblem in a Leetcode discussio' -> 'oblem in a(Leetcode) discussio'
en7 English yamih23436 2021-06-08 14:56:52 1 Tiny change: 'ute force ? \n\nExa' -> 'ute force ? \n\nExa'
en6 English yamih23436 2021-06-08 14:56:19 14 Tiny change: 'n$ejk$\n\n' -> 'n$ejk$\n\nAny ideas ? \n'
en5 English yamih23436 2021-06-08 07:45:45 2 Tiny change: 'n{$abc, bfg, cgk, ade' -> 'n{$abc, bfj, cgk, ade'
en4 English yamih23436 2021-06-08 07:45:10 8
en3 English yamih23436 2021-06-08 07:43:27 174
en2 English yamih23436 2021-06-08 07:42:41 11
en1 English yamih23436 2021-06-08 07:42:05 641 Initial revision (published)