fork(1) 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);
  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) {
  54.         List<TrieNode> res = new ArrayList<>();
  55.         if (ind >= prefix.length()) {
  56.             return Collections.singletonList(node);
  57.         }
  58.         char charOfPrefix = prefix.charAt(ind);
  59.         if (node.map.containsKey(charOfPrefix)) {
  60.             res.addAll(getStartNodes(node.map.get(charOfPrefix), prefix, ind + 1, errors));
  61.         }
  62.         if (errors < ERRORS_ALLOWED) {
  63.             for (char c : node.map.keySet()) {
  64.                 if (node.map.containsKey(charOfPrefix) && c == charOfPrefix) {
  65.                     continue;
  66.                 }
  67.                 List<TrieNode> withPrefixShift = getStartNodes(node.map.get(c), prefix, ind + 1, errors + 1);
  68.                 res.addAll(withPrefixShift);
  69.                 if (withPrefixShift.isEmpty()) {
  70.                     res.addAll(getStartNodes(node.map.get(c), prefix, ind, errors + 1));
  71.                 }
  72.             }
  73.         }
  74.         return res;
  75.     }
  76.  
  77.     public static void main(String[] args) {
  78.         testSkipNotNeeded();
  79.         testSkipNeeded();
  80.     }
  81.  
  82.     /**
  83.      * Removing condition at line 69 leads to duplicate "abzd"
  84.      */
  85.     static void testSkipNotNeeded() {
  86.         List<String> dictionary = List.of("abc", "doecm", "abzd", "azfs", "kzcs");
  87.         Solution solution = new Solution(dictionary);
  88.         List<String> words = solution.getWords("abc");
  89.         System.out.println(words);
  90.     }
  91.  
  92.     /**
  93.      * Removing lines 69-71 leads to empty result
  94.      */
  95.     static void testSkipNeeded() {
  96.         List<String> dictionary = List.of("abzd", "helloaaa");
  97.         Solution solution = new Solution(dictionary);
  98.         List<String> words = solution.getWords("heoaa");
  99.         System.out.println(words);
  100.     }
  101. }
  102.  
Success #stdin #stdout 0.08s 51232KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
[abc, abzd, azfs, kzcs]
[helloaaa]
https://ideone.com/WLhdmP
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!