Word Squares

题目地址：
https://leetcode.com/problems/word-squares/description/

题目：

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

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

解题思路：
这道题常规解法就是每次选一个开始的string，然后看该string的每一个char是否可以在输入中找到以该char开始的string。

代码：

public static void main(String[] args){
        WordSquares wordSquares = new WordSquares();
//        String[] words = {"area","lead","wall","lady","ball"};        String[] words = {"momy","oooo","yoyo"};
        List<List<String>> rst = wordSquares.wordSquares(words);
        System.out.println(rst);
    }

    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> rst = new ArrayList<>();
        if(words == null || words.length == 0){
            return rst;
        }
        int wordLen = words[0].length();
//        if(words.length < wordLen){//            return rst;//        }        // build an array of list with length of 26 to check if there is any word starts with character        // in the first word        List[] buffer = new List[26];
        for(int i = 0; i <= words.length - 1; i++){
            char c = words[i].charAt(0);
            if(buffer[c - 'a'] == null){
                buffer[c - 'a'] = new ArrayList();
            }
            buffer[c - 'a'].add(words[i]);
        }
        for(int i = 0; i <= words.length - 1; i++){
            List<List<String>> temp = construct(buffer, words[i]);
            if(temp == null || temp.size() == 0){
                continue;
            }
            for(int j = 0; j <= temp.size() - 1; j++){
                boolean valid = validWordSquare(temp.get(j)); // check is the method that we had before                if(valid){
                    rst.add(temp.get(j));
                }
            }
        }
        return rst;
    }

    // aggregate the words    private List<List<String>> construct(List<String>[] buffer, String word) {
        List<List<String>> rst = new ArrayList<>();
        List<String> list = new ArrayList<>();
        list.add(word);
        rst.add(list);
        for(int i = 1; i <= word.length() - 1; i++){
            if(buffer[word.charAt(i) - 'a'] == null){
                return new ArrayList<>();
            }
            else{
                char c = word.charAt(i);
                if(buffer[c - 'a'].size() == 1){
                    for(int j = 0; j <= rst.size() - 1; j++){
                        rst.get(j).add(buffer[c - 'a'].get(0));
                    }
                }
                else{
                    int addSize = buffer[c - 'a'].size();
                    Queue<List<String>> queue = new LinkedList<>();
                    int queueSize = rst.size();
                    // put list in rst into queue                    for(int j = 0; j <= queueSize - 1; j++){
                        queue.offer(new ArrayList<>(rst.get(j)));
                    }
                    rst = new ArrayList<>();
                    // double loop and add the string from the buf to the list from the queue                    // one by one and add them temp rst to rst                    for(int j = 0; j <= queueSize - 1; j++){
                        List<String> temp = queue.poll();
                        for(int k = 0; k <= addSize - 1; k++){
                            List<String> curr = new ArrayList<>(temp);
                            curr.add(buffer[c - 'a'].get(k));
                            rst.add(curr);
                        }
                    }
                }
            }
        }
        return rst;
    }


    public boolean validWordSquare(List<String> words) {
        if(words == null || words.size() == 0){
            return true;
        }
        int row = words.size();
        int maxRowLen = 0;
        for(int i = 0; i <= row - 1; i++){
            maxRowLen = Math.max(words.get(i).length(), maxRowLen);
        }
        int size = Math.max(row, maxRowLen);
        char[][] matrix = convert(words, size);
        for(int i = 0; i<= size - 1; i++){
            for(int j = i + 1; j <= size - 1; j++){
                if(matrix[i][j] != matrix[j][i]){
                    return false;
                }
            }
        }
        return true;
    }

    private char[][] convert(List<String> words, int size) {
        int row = words.size();
        char[][] rst = new char[size][size];
        int i = 0;
        for(; i <= row - 1; i++){
            int j = 0;
            for(char c : words.get(i).toCharArray()){
                rst[i][j] = c;
                j++;
            }
            while(j <= size - 1){
                rst[i][j] = ' ';
                j++;
            }
        }
        while(i <= size - 1){
            int j = 0;
            while(j <= size - 1){
                rst[i][j] = ' ';
                j++;
            }
            i++;
        }
        return rst;
    }

This approach get TLE, so we need to try some other method:
Link: https://discuss.leetcode.com/topic/63516/explained-my-java-solution-using-trie-126ms-16-16

Code for using HashMap:
map的建立就相当于根据prefix找word。

public List<List<String>> wordSquares(String[] words) {
    List<List<String>> ret = new ArrayList<List<String>>();
    if(words.length==0 || words[0].length()==0) return ret;
    Map<String, Set<String>> map = new HashMap<>();
    int squareLen = words[0].length();
    // create all prefix    
    for(int i=0;i<words.length;i++){
        for(int j=-1;j<words[0].length();j++){
            if(!map.containsKey(words[i].substring(0, j+1))) 
                map.put(words[i].substring(0, j+1), new HashSet<String>());
            map.get(words[i].substring(0, j+1)).add(words[i]);
        }
    }
    helper(ret, new ArrayList<String>(), 0, squareLen, map);
    return ret;
}
public void helper(List<List<String>> ret, List<String> cur, int matched, int total, Map<String, Set<String>> map){
    if(matched == total) {ret.add(new ArrayList<String>(cur));return;}
    // build search string    
    StringBuilder sb = new StringBuilder();
    for(int i=0;i<=matched-1;i++) 
        sb.append(cur.get(i).charAt(matched));
    // bachtracking    
    Set<String> cand = map.get(sb.toString());
    if(cand==null) return;
    for(String str:cand){
        cur.add(str);
        helper(ret, cur, matched+1, total, map);
        cur.remove(cur.size()-1);
    }
}

Code for using trie:

 class TrieNode {
    List<String> startWith;
    TrieNode[] children;

    TrieNode() {
        startWith = new ArrayList<>();
        children = new TrieNode[26];
    }
}

class Trie {
    TrieNode root;

    Trie(String[] words) {
        root = new TrieNode();
        for (String w : words) {
            TrieNode cur = root;
            for (char ch : w.toCharArray()) {
                int idx = ch - 'a';
                if (cur.children[idx] == null)
                    cur.children[idx] = new TrieNode();
                cur.children[idx].startWith.add(w);
                cur = cur.children[idx];
            }
        }
    }

    List<String> findByPrefix(String prefix) {
        List<String> ans = new ArrayList<>();
        TrieNode cur = root;
        for (char ch : prefix.toCharArray()) {
            int idx = ch - 'a';
            if (cur.children[idx] == null)
                return ans;

            cur = cur.children[idx];
        }
        ans.addAll(cur.startWith);
        return ans;
    }
}

public List<List<String>> wordSquares(String[] words) {
    List<List<String>> ans = new ArrayList<>();
    if (words == null || words.length == 0)
        return ans;
    int len = words[0].length();
    Trie trie = new Trie(words);
    List<String> ansBuilder = new ArrayList<>();
    for (String w : words) {
        ansBuilder.add(w);
        search(len, trie, ans, ansBuilder);
        ansBuilder.remove(ansBuilder.size() - 1);
    }

    return ans;
}

private void search(int len, Trie tr, List<List<String>> ans,
                    List<String> ansBuilder) {
    if (ansBuilder.size() == len) {
        ans.add(new ArrayList<>(ansBuilder));
        return;
    }

    int idx = ansBuilder.size();
    StringBuilder prefixBuilder = new StringBuilder();
    for (String s : ansBuilder)
        prefixBuilder.append(s.charAt(idx));
    List<String> startWith = tr.findByPrefix(prefixBuilder.toString());
    for (String sw : startWith) {
        ansBuilder.add(sw);
        search(len, tr, ans, ansBuilder);
        ansBuilder.remove(ansBuilder.size() - 1);
    }
}