Given a set of words (without duplicates), find all  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 la r e al e a dl a d y

Note:

1. There are at least 1 and at most 1000 words.
2. All words will have the exact same length.
3. Word length is at least 1 and at most 5.
4. 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).

class Solution {public:    vector
     
      
       > wordSquares(vector
       
        & words) {        vector
        
         
          > res;        unordered_map
          
           > m; int n = words[0].size(); for (string word : words) { for (int i = 0; i < n; ++i) { string key = word.substr(0, i); m[key].insert(word); } } vector
           
            
             > mat(n, vector
             
              (n)); helper(0, n, mat, m, res); return res; } void helper(int i, int n, vector
              
               
                >& mat, unordered_map
                
                 >& m, vector
                 
                  
                   >& res) { if (i == n) { vector
                   
                     out; for (int j = 0; j < n; ++j) out.push_back(string(mat[j].begin(), mat[j].end())); res.push_back(out); return; } string key = string(mat[i].begin(), mat[i].begin() + i); for (string str : m[key]) { mat[i][i] = str[i]; int j = i + 1; for (; j < n; ++j) { mat[i][j] = str[j]; mat[j][i] = str[j]; if (!m.count(string(mat[j].begin(), mat[j].begin() + i + 1))) break; } if (j == n) helper(i + 1, n, mat, m, res); } }};