425. Word Squares

DFS + Backtracking + HashMap

T: O(N*26^L), N words[] size, L is word len

class Solution {
    public List<List<String>> wordSquares(String[] words) {
        Map<String, List<String>> map = prefixMapWords(words);
        List<List<String>> res = new ArrayList<>();
        List<String> square = new ArrayList<>();
        for (String word : words) {
            square.add(word);
            search(map, res, square);
            square.remove(square.size()-1);
        }
        return res;
    }
    private Map<String, List<String>> prefixMapWords(String[] words) {
        Map<String, List<String>> map = new HashMap<>();
        for (String word : words) {
            for (int i = 0; i < word.length(); i++) {
                String prefix = word.substring(0, i+1);
                map.putIfAbsent(prefix, new ArrayList<>());
                map.get(prefix).add(word);
            }
        }
        return map;
    }
    private void search(Map<String, List<String>> map, List<List<String>> res, List<String> square) {
        int rowCount = square.get(0).length();
        int rowIndex = square.size();
        
        if (rowIndex == rowCount) {
            res.add(new ArrayList<>(square));
            return;
        }
        
        
        StringBuilder prefix = new StringBuilder();
        for (String s : square) {
            prefix.append(s.charAt(rowIndex));
        }
        
        List<String> wordWithPrefix = map.getOrDefault(prefix.toString(), new ArrayList<>());
        for (String word : wordWithPrefix) {
            square.add(word);
            search(map, res, square);
            square.remove(square.size()-1);
        }
    }
}

/*
1. generate a prefix map for each word's prefix, map<String, List<String>>

2. each word can be the square's first line,
so dfs each word (backtracking)

3. in dfs 
terminal condition: if rowCnt == rowIndex => add ans to res
make curr prefix

4. 
get this prefix's mapping words(List)
dfs these words(backtracking) agian

*/

pruning version

before processing one prefix, we can check all prefix is existed in map

        for (int i = rowIndex; i < rowCount; i++) {
            StringBuilder prefix = new StringBuilder();
            for (String s : square) {
                prefix.append(s.charAt(rowIndex));
            }
            if (!map.containsKey(prefix.toString())) {
                return;
            }
        }

class Solution {
    public List<List<String>> wordSquares(String[] words) {
        Map<String, List<String>> map = prefixMapWords(words);
        List<List<String>> res = new ArrayList<>();
        List<String> square = new ArrayList<>();
        for (String word : words) {
            square.add(word);
            search(map, res, square);
            square.remove(square.size()-1);
        }
        return res;
    }
    
    private Map<String, List<String>> prefixMapWords(String[] words) {
        Map<String, List<String>> map = new HashMap<>();
        for (String word : words) {
            for (int i = 0; i < word.length(); i++) {
                String prefix = word.substring(0, i+1);
                map.putIfAbsent(prefix, new ArrayList<>());
                map.get(prefix).add(word);
            }
        }
        return map;
    }
    private void search(Map<String, List<String>> map, List<List<String>> res, List<String> square) {
        int rowCount = square.get(0).length();
        int rowIndex = square.size();
        
        if (rowIndex == rowCount) {
            res.add(new ArrayList<>(square));
            return;
        }
        
        for (int i = rowIndex; i < rowCount; i++) {
            StringBuilder prefix = new StringBuilder();
            for (String s : square) {
                prefix.append(s.charAt(rowIndex));
            }
            if (!map.containsKey(prefix.toString())) {
                return;
            }
        }
        
        StringBuilder prefix = new StringBuilder();
        for (String s : square) {
            prefix.append(s.charAt(rowIndex));
        }
        
        List<String> wordWithPrefix = map.getOrDefault(prefix.toString(), new ArrayList<>());
        for (String word : wordWithPrefix) {
            square.add(word);
            search(map, res, square);
            square.remove(square.size()-1);
        }
    }
}

/*
1. generate a prefix map for each word's prefix, map<String, List<String>>

2. each word can be the square's first line,
so dfs each word (backtracking)

3. in dfs 
terminal condition: if rowCnt == rowIndex => add ans to res
make curr prefix

4. 
get this prefix's mapping words(List)
dfs these words(backtracking) agian

*/