nikunjsoni

425

Jun 26th, 2021
112
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int n;
  4.     unordered_map<string, vector<string>> fulls;
  5.     vector<string> square;
  6.     vector<vector<string>> squares;
  7.    
  8.     vector<vector<string>> wordSquares(vector<string>& words) {
  9.         n = words[0].size();
  10.         square.resize(n);
  11.         for(string word : words)
  12.             for(int i=0; i<n; i++)
  13.                 fulls[word.substr(0, i)].push_back(word);
  14.         build(0);
  15.         return squares;
  16.     }
  17.    
  18.     void build(int i) {
  19.         if(i == n) {
  20.             squares.push_back(square);
  21.             return;
  22.         }
  23.         string prefix;
  24.         for(int k=0; k<i; k++)
  25.             prefix += square[k][i];
  26.         for(string word : fulls[prefix]) {
  27.             square[i] = word;
  28.             build(i + 1);
  29.         }
  30.     }
  31. };
RAW Paste Data