LeetCode 425. Word Squares

Given a set of words (without duplicates), find all word squares 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 l
a r e a
l e a d
l 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).

/////////////////////////////////////////////////////////////////////////////

for (auto word:s)
    vector<vector<string>> res;
    vector<string> tmp;
    tmp.push_back(word);
    for(int i=1;i<word.size();i++)tmp.push_back(word[i]);
    int col=1;
    bt(&s, &res, &tmp, col){
         if(col==word.size())res.push_back(tmp);
         else{
               string subs=tmp[col];
               for(auto w:s){
                    if(word.substr(0, subs.size())==subs){
                         ..update tmp
                         bt(s, res, tmp, col+1);
                         ..de-update tmp
                    }
               }
        }
  }
};