Java recursion solution


  • 0
    D

    Idea is learned from @lzb700m. The solution is written in recursion. This recursion is a hybrid of top-down and bottom-up paradigm.

    public class Solution {
        public List<List<String>> wordSquares(String[] words) {
            if (words == null || words.length == 0) {
                return new ArrayList<>();
            }
            Map<String, List<String>> prefixmap = new HashMap<>();
            for (String word : words) {
                for (int end = 0; end < word.length(); end++) {
                    String prefix = word.substring(0, end);
                    if (!prefixmap.containsKey(prefix)) {
                        prefixmap.put(prefix, new ArrayList<>());
                    }
                    prefixmap.get(prefix).add(word);
                }
            }
            return wordSquares("", words[0].length(), new ArrayList<String>(), prefixmap);
        }
    
        private List<List<String>> wordSquares(String prefix, int len, List<String> previous, Map<String, List<String>> prefixmap) {
            List<List<String>> ret = new ArrayList<>();
            int level = prefix.length();
            if (level == len) {
                ret.add(new ArrayList<>());
                return ret;
            }
            if (prefixmap.containsKey(prefix)) {
                List<String> candidates = prefixmap.get(prefix);
                for (String candidate : candidates) {
                    previous.add(candidate);
                    StringBuffer newprefixsb = new StringBuffer();
                    for (String str : previous) {
                        newprefixsb.append(level < len - 1 ? str.charAt(level + 1) : 'x');
                    }
                    for (List<String> child : wordSquares(newprefixsb.toString(), len, previous, prefixmap)) {
                        List<String> answer = new ArrayList<>();
                        answer.add(candidate);
                        answer.addAll(child);
                        ret.add(answer);
                    }
                    previous.remove(previous.size() - 1);
                }
            }
            return ret;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.