425 Word Square

Description

Given a set of words(without duplicates), find allword squaresyou can build from them.

A sequence of words forms a valid word square if thekthrow 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).

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).

想法：

1. 可以用dfs，逐个尝试。在尝试的过程中，验证是否现在的结果是否符合条件。

2. 如果只用尝试通过验证了的candidates，那么就会有“砍枝”的优化发生。

   * 那么情况就成了：

   放入 baba，
   
   下一个candidate 一定要以a开头，abat, atan, atal。
   
   放入abat，
   
   下一个candidate 一定要以ba开头, baba
   
   放入baba,
   
   下一个candidate 一定要以ata开头，atal。
   
   放入atal.
   

   * 通过以上过程，可以想象Trie是最合适的数据结构。

   * 那么算法就是Trie + dfs + trackback。

例程：

/*
* This code includes Debug Code, please ignore.
*/
class Trie {
public:
    Trie* trie[256];
    vector<string*> candidates;
    Trie() {
        for(int loop = 0; loop < 256; ++loop) {
            trie[loop] = nullptr;
        }
    }

    void insert(string* word) {
        Trie *tmp = this;
        this->candidates.push_back(word);
       #ifdef TEST
        cout << "insert: " << *word << endl;
       #endif
        for(auto iter = (*word).begin(); iter != (*word).end(); ++iter) {
            //cout << *iter << endl;
            if(nullptr == tmp->trie[(*iter) - 'a']) {
                tmp->trie[(*iter) - 'a'] = new Trie();
            }
            //cout << (*iter) - 'a' << endl;
            tmp = tmp->trie[(*iter) - 'a'];
            tmp->candidates.push_back(word);
            #ifdef TEST
            if(nullptr != tmp)  {
                cout << (*iter) << endl;
                copy(tmp->candidates.begin(), tmp->candidates.end(), ostream_iterator<string>(cout, ","));
                cout << endl;
            }
            #endif
            //cout << "close: " << word << endl;
        }
    }

    Trie* search(const string& word) {
        Trie *tmp = this;
        for(auto iter = word.begin(); iter != word.end(); ++iter) {
            if(nullptr == tmp->trie[(*iter) - 'a']) {
                //cout << *iter << " not found" << endl;
                tmp = nullptr;
                break;
            }
            tmp = tmp->trie[(*iter) - 'a'];
        }
        #ifdef TEST
        cout << "search: " << word << endl;
        if(nullptr != tmp)  {
            cout << "candidates - " << endl;
            copy(tmp->candidates.begin(), tmp->candidates.end(), ostream_iterator<string>(cout, ","));
            cout << endl;
        }
        #endif
        return (word.size() == 0) ? this : tmp;
    }
    //friend void Solution::dfs(vector<vector<string>>& rst, vector<string> &candidate, string &elem, int index);
};

class Solution {
private:
    int wordSize = 0;
    int wordsCnt = 0;
    Trie root;

public:
    vector<vector<string>> wordSquares(vector<string>& words) {
        vector<vector<string>> rst;
        vector<string> candidate;

        cout << "test0" << endl;
        if(0 != words.size()) {
            wordSize = words[0].size();
            wordsCnt = words.size();
            cout << wordSize << "-" << wordsCnt << endl;
            //if(wordSize <= wordsCnt) 
            {
                for(int loop = 0; loop < words.size(); ++loop) {
                    root.insert(&words[loop]);
                }
                cout << "test1" << endl;
                dfs(rst, candidate, "", 1);
            }
        }
        cout << "test2" << endl;
        return rst;
    }

    //["abat","baba","atan","atal"]
    void dfs(vector<vector<string>>& rst, vector<string> &candidate, const string& next, int index) {
        if(candidate.size() == wordSize) {
            rst.push_back(candidate);
            return;
        }

        Trie *tmp = this->root.search(next);
       #ifdef TEST
        cout << next << ":" << endl;
        if(nullptr != tmp)
            copy(tmp->candidates.begin(), tmp->candidates.end(), ostream_iterator<string>(cout, ","));
        cout << endl;
       #endif

        if(nullptr != tmp) {
            for(auto iter = tmp->candidates.begin(); iter != tmp->candidates.end(); ++iter) {
                string next;
                //cout << *iter << endl;

                candidate.push_back(*(*iter));

                for(int loop = 0; loop < candidate.size(); ++loop) {
                    next += candidate[loop][index];
                }

                //elem.push_back((*iter)[index]);
                dfs(rst, candidate, next, index + 1);
                next.erase();

                //elem.pop_back();
                candidate.pop_back();
            }
        }
    }
};