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


  • 0
    B

    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)
            result.add(node.index);
          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;
        }
    

Log in to reply
 

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