121ms Java solution using Trie and BackTracking


  • 4
    W
    public class Solution {
        TrieNode root = new TrieNode();
        public List<List<String>> wordSquares(String[] words) {
            List<List<String>> ans = new ArrayList<>();
            if(words.length == 0) return ans;
            buildTrie(words);
            int length = words[0].length();
            findSquare(ans, length, new ArrayList<>());
            return ans;
        }
        
        private void findSquare(List<List<String>> ans, int length, List<String> temp) {
            if(temp.size() == length) {
                ans.add(new ArrayList<>(temp));
                return;
            }
            int index = temp.size();
            StringBuilder sb = new StringBuilder();
            for(String s : temp) {
                sb.append(s.charAt(index));
            }
            String s = sb.toString();
            TrieNode node = root;
            for(int i = 0; i < s.length(); i++) {
                if(node.next[s.charAt(i) - 'a'] != null) {
                    node = node.next[s.charAt(i) - 'a'];
                } else {
                    node = null;
                    break;
                }
            }
            if(node != null) {
                for(String next : node.words) {
                    temp.add(next);
                    findSquare(ans, length, temp);
                    temp.remove(temp.size() - 1);
                }
            }
        }
        
        private void buildTrie(String[] words) {
            for(String word : words) {
                TrieNode node = root;
                char[] array = word.toCharArray();
                for(char c : array) {
                    node.words.add(word);
                    if(node.next[c - 'a'] == null) {
                        node.next[c - 'a'] = new TrieNode();
                    }
                    node = node.next[c - 'a'];
                }
                node.words.add(word);
            }
        }
        
        class TrieNode {
            TrieNode[] next = new TrieNode[26];
            List<String> words = new ArrayList<>();
        }
    }

  • 0

    can you please add time complexity analysis as well?


Log in to reply
 

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