fork download
copy 
  1. import java.util.*;
  2.  
  3. /*
  4. To avoid duplicates with with skips we need to find start nodes that are as close as possible to the root
  5. If it is not possible to find a node for a prefix with a given amount of errors, ONLY then we try to apply skips
  6.  */
  7.  
  8. class Solution {
  9.  
  10.     static final int ERRORS_ALLOWED = 2;
  11.  
  12.     static class TrieNode {
  13.         Map<Character, TrieNode> map = new HashMap<>();
  14.         String word = null;
  15.     }
  16.  
  17.     TrieNode root = new TrieNode();
  18.  
  19.     public Solution(List<String> dictionary) {
  20.         for (String word : dictionary) {
  21.             TrieNode cur = root;
  22.             for (char c : word.toCharArray()) {
  23.                 if (!cur.map.containsKey(c)) {
  24.                     TrieNode next = new TrieNode();
  25.                     cur.map.put(c, next);
  26.                 }
  27.                 cur = cur.map.get(c);
  28.             }
  29.             cur.word = word;
  30.         }
  31.     }
  32.  
  33.     List<String> getWords(String prefix) {
  34.         List<TrieNode> startNodes = getStartNodes(root, prefix, 0, 0, new HashSet<>());
  35.         List<String> words = new ArrayList<>();
  36.         for (TrieNode node : startNodes) {
  37.             words.addAll(getAllWords(node));
  38.         }
  39.         return words;
  40.     }
  41.  
  42.     private List<String> getAllWords(TrieNode node) {
  43.         List<String> words = new ArrayList<>();
  44.         if (node.word != null) {
  45.             words.add(node.word);
  46.         }
  47.         for (TrieNode next : node.map.values()) {
  48.             words.addAll(getAllWords(next));
  49.         }
  50.         return words;
  51.     }
  52.  
  53.     private List<TrieNode> getStartNodes(TrieNode node, String prefix, int ind, int errors, Set<TrieNode> visited) {
  54.         List<TrieNode> res = new ArrayList<>();
  55.         if (visited.contains(node)) {
  56.             return res;
  57.         }
  58.         if (ind >= prefix.length()) {
  59.             visited.addAll(traverse(node));
  60.             return Collections.singletonList(node);
  61.         }
  62.         char charOfPrefix = prefix.charAt(ind);
  63.         if (node.map.containsKey(charOfPrefix)) {
  64.             res.addAll(getStartNodes(node.map.get(charOfPrefix), prefix, ind + 1, errors, visited));
  65.         }
  66.         if (errors < ERRORS_ALLOWED) {
  67.             for (char c : node.map.keySet()) {
  68.                 if (node.map.containsKey(charOfPrefix) && c == charOfPrefix) {
  69.                     continue;
  70.                 }
  71.                 List<TrieNode> withPrefixShift = getStartNodes(node.map.get(c), prefix, ind + 1, errors + 1, visited);
  72.                 res.addAll(withPrefixShift);
  73.                 res.addAll(getStartNodes(node.map.get(c), prefix, ind, errors + 1, visited));
  74.             }
  75.         }
  76.         return res;
  77.     }
  78.  
  79.     private List<TrieNode> traverse(TrieNode node) {
  80.         List<TrieNode> treeNodes = new ArrayList<>();
  81.         treeNodes.add(node);
  82.  
  83.         for (TrieNode next : node.map.values()) {
  84.             treeNodes.addAll(traverse(next));
  85.         }
  86.  
  87.         return treeNodes;
  88.     }
  89.  
  90.     public static void main(String[] args) {
  91.         testSkipNotNeeded();
  92.         testSkipNeeded();
  93.     }
  94.  
  95.  
  96.     static void testSkipNotNeeded() {
  97.         List<String> dictionary = List.of("abc", "doecm", "abzd", "azfs", "kzcs");
  98.         Solution solution = new Solution(dictionary);
  99.         List<String> words = solution.getWords("abc");
  100.         System.out.println(words);
  101.     }
  102.  
  103.     static void testSkipNeeded() {
  104.         List<String> dictionary = List.of("abzd", "helloaaa", "heoaabb", "heloaabb");
  105.         Solution solution = new Solution(dictionary);
  106.         List<String> words = solution.getWords("heoaa");
  107.         System.out.println(words);
  108.     }
  109. }
  110.  
Success #stdin #stdout 0.08s 47008KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
[abc, abzd, azfs, kzcs]
[heoaabb, heloaabb, helloaaa]
https://ideone.com/ZrQWPn
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!