LintCode 634: Word Square (搜索经典题！！！)

634. Word Squares
     中文English
     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
Example
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”]]
Notice
There are at least 1 and at most 1000 words.
All words will have the exact same length.
Word length is at least 1 and at most 5.
Each word contains only lowercase English alphabet a-z.

这题关键是要能根据字符串的前缀找到与之相匹配的字符串们。方法有两个: hashmap (prefix vs matches_strings) 和 Trie。

解法1：用hashmap。虽然知道思路，可是还是感觉很难。参考的网上的答案。
举例如下：
words = [“area”,“lead”,“wall”,“lady”,“ball”]
我们先让prefix[""]=words, 然后将所有字符串的的前缀和对应字符串都放到prefix 这个hash table里面。
squares[][]这个里面是放已经找好的words，当已经找到了wordLen个字符串之后就是一个可行解了，放到results里面。
checkPrefix(index, nextWord)这个函数是在第index+1到wordLen的列中，找第0到index - 1行中找到pre前缀。

比如说squares = [wall, area, lead]
index = 3，此时pre遍历squares，把每个字符串的第3个字符拼起来，即lad，然后再与还不在squares中的字符串(lady, ball)的第3个字符挨个拼起来，看是不是在prefix里面。这里先处理lady, lad+y=lady，在prefix里面，所以squares=[wall, area, lead, lady]是一个可行解，放入results。

注意：

1. dfs里面每次循环都必须从0开始。

代码如下：

class Solution {
public:/*** @param words a set of words without duplicates* @return all word squares*/void initPrefix(vector & words) {int n = words.size();prefix[""] = words;for (int i = 0; i < n; ++i) {int m = words[i].size();for (int j = 0; j < m; ++j) {prefix[words[i].substr(0, j + 1)].push_back(words[i]);}}}bool checkPrefix(int index, string nextWord) {for (int i = index + 1; i < wordLen; ++i) {string pre;for (int j = 0; j < index; ++j) {pre += squares[j][i];}pre += nextWord[i];if (prefix.find(pre) == prefix.end()) {return false;}}return true;}void dfs(int index) {if (index == wordLen) {results.push_back(squares);return;}string pre;for (int i = 0; i < index; ++i) {pre += squares[i][index];}vector matchedWords = prefix[pre];int m = matchedWords.size();for (int i = 0; i < m; ++i) {if (!checkPrefix(index, matchedWords[i])) {continue;}squares.push_back(matchedWords[i]);dfs(index + 1);squares.pop_back();}}vector> wordSquares(vector& words) {if (words.size() == 0) return results;initPrefix(words);wordLen = words[0].size();dfs(0);return results;}private:int wordLen;unordered_map> prefix;vector squares;vector> results;
};

解法2： Trie
TBD

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！