valid word square

class Solution {
    public boolean validWordSquare(List<String> words) {

        for (int i = 0; i < words.size(); i++) {            
            for (int j = 0; j < words.get(i).length(); j++) {                
                if (j >= words.size() || i >= words.get(j).length()) return false;
                if (words.get(i).charAt(j) != words.get(j).charAt(i)) return false;
            }
        }        
        return true;
    }
}

word square

• store all possible words on node
• use hash, key is prefix, value can be list of possible words, or hasword anything...

public class Solution {
    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, 1);
            ansBuilder.remove(ansBuilder.size() - 1);
        }

        return ans;
    }

    private void search(int len, Trie tr, List<List<String>> ans,
            List<String> ansBuilder, int idx) {
        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, idx+1);
            ansBuilder.remove(ansBuilder.size() - 1);
        }
    }
}

public class Solution {

    int wordLen;
    Map<String, List<String>> hash = new HashMap<>();
    List<String> squares = new ArrayList<>();
    List<List<String>> ans = new ArrayList<>();

    void initPrefix(String[] words) {
        for (String item : words) {
            hash.putIfAbsent("", new ArrayList<>());
            hash.get("").add(item);

            String pre = "";
            for (char c : item.toCharArray()) {
                pre += c;
                hash.putIfAbsent(pre, new ArrayList<>());
                hash.get(pre).add(item);
            }
        }
    }

    boolean checkPrefix(int l, String nextWord) {
        for (int j = l + 1; j < wordLen; j++) {
            String pre = "";
            for (int k = 0; k < l; k++) {
                pre = pre + squares.get(k).charAt(j);
            }
            pre += nextWord.charAt(j);
            if (!hash.containsKey(pre)) {
                return false;
            }
        }
        return true;
    }

    void dfs(int l) {
        if (l == wordLen) {
            ans.add(new ArrayList<>(squares));
            return;
        }
        String pre = "";
        for (int i = 0; i < l; i++)
            pre += squares.get(i).charAt(l);
        List<String> w = hash.get(pre);

        for (String item : w) {
            if (!checkPrefix(l, item)) {
                continue;
            }
            squares.add(item);
            dfs(l + 1);
            squares.remove(squares.size() - 1);
        }
    }

    public List<List<String>> wordSquares(String[] words) {
        // Write your code here
        if (words.length == 0) {
            return ans;
        }
        initPrefix(words);
        wordLen = words[0].length();
        dfs(0);
        return ans;
    }
}

word search ii:

• 先update rst 再判return 的情况
• 不 return 继续往下找 因为可能存在更长的
• 要用 put. 有true一定要为true e.g. "ab" "abb"

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        Map<String, Boolean> hash = initPrefixTree(words);
        List<String> rst = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(rst, board, hash, i, j, sb);       
            }
        }        
        return rst;
    }

    int[] dx = new int[] {1,0,-1,0};
    int[] dy = new int[] {0,1,0,-1};
    private void dfs(List<String> rst, char[][] board, Map<String, Boolean> hash, int i, int j, StringBuilder sb) {
        //先update rst 再判return 的情况
        if (!hash.containsKey(sb.toString())) return;
        if (hash.get(sb.toString())) {            
            if (!rst.contains(sb.toString()))
                rst.add(new String(sb.toString())); // 不 return 继续往下找 因为可能存在更长的
        }

        if (i > board.length - 1 || i < 0 || j > board[0].length - 1 || j < 0) return;

        for (int n = 0; n < 4; n++) {            
            sb.append(board[i][j]);
            char tmp = board[i][j];            
            board[i][j] = '#';            
            dfs(rst, board, hash, i + dx[n], j + dy[n], sb);        
            board[i][j] = tmp;
            sb.deleteCharAt(sb.length()-1);
        }
    }

    private static Map<String, Boolean> initPrefixTree(String[] words) {
        Map<String, Boolean> hash = new TreeMap<>();
        for (String word : words) {
            hash.putIfAbsent("", false);

            StringBuilder sb = new StringBuilder();
            for (char c : word.toCharArray()) {
                sb.append(c);
                hash.putIfAbsent(sb.toString(), false); // 要用 putIfAbsent. 避免覆盖true的情况
            }
            hash.put(sb.toString(), true);  // 要用 put. 有true一定要为true  e.g. "ab" "abb"
        }
        return hash;
    }
}