# Trie solutions DO NOT guarantee O(NK^2) time complexity, do they???

• counter example:

{"a", "aa", "aaa", "aaaa", "aaaaa"}

assume there are N words.
searching the word in the Trie yields at most N-1 candidates.
the searching step itself is O(K) where K is the average length of the words.
verifying each candidate is also O(K).

The worst case is O(N^2 * K^2)?

Or am I missing something important here?

My Trie solution code for reference. (faster than 60% only):

``````    public List<List<Integer>> palindromePairs(String[] words) {
TrieNode trie = indexWordsReversely(words);
List<List<Integer>> result = new ArrayList<>();
for(int i = 0; i < words.length; i++) {
String word = words[i];
for(int matched : findWordsWithPrefix(word, trie)) {
if(matched == i) continue;
String candidate = words[matched];
if(candidate.length() > word.length()) {
if(isPalindrome(candidate, 0, candidate.length() - word.length() - 1)) result.add(Arrays.asList(i, matched));
} else {
if(isPalindrome(word, candidate.length(), word.length() - 1)) result.add(Arrays.asList(i, matched));
}
}
}
return result;
}

private static TrieNode indexWordsReversely(String[] words) {
TrieNode root = new TrieNode();
for(int i = 0; i < words.length; i++) {
String word = words[i];
indexWordReversely(word, word.length() - 1, root).index = i;
}
return root;
}

private static TrieNode indexWordReversely(String word, int offset, TrieNode node) {
if(offset == -1) return node;
int c = word.charAt(offset) - 'a';
if(node.children[c] == null) node.children[c] = new TrieNode();
return indexWordReversely(word, offset - 1, node.children[c]);
}

private static List<Integer> findWordsWithPrefix(String prefix, TrieNode root) {
List<Integer> ret = new ArrayList<>();
search(prefix, 0, root, ret);
return ret;
}

private static void search(String word, int offset, TrieNode node, List<Integer> result) {
if(node.index != -1)
if(offset == word.length()) {
for(TrieNode child : node.children) {
if(child != null) search(word, offset, child, result);
}
} else {
int c = word.charAt(offset) - 'a';
TrieNode child = node.children[c];
if(child != null) search(word, offset + 1, child, result);
}
}

private static boolean isPalindrome(String word, int start, int end) {
while(start < end) {
if(word.charAt(start) != word.charAt(end)) return false;
start++;
end--;
}
return true;
}

private static class TrieNode {
private TrieNode[] children = new TrieNode[26];
private int index = -1;
}
``````

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