SHARE
TWEET

Untitled

a guest Feb 16th, 2020 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.company;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.HashMap;
  5. import java.util.HashSet;
  6. import java.util.List;
  7. import java.util.Map;
  8. import java.util.Set;
  9.  
  10. public class Main {
  11.  
  12.     static class Node {
  13.         public char c;
  14.         public Map<Character, Node> next = new HashMap<>();
  15.         public boolean leaf = false;
  16.  
  17.         public Node(char c) {
  18.             this.c = c;
  19.         }
  20.     }
  21.  
  22.     static Node build(String[] words) {
  23.         Node node = new Node('-');
  24.         for (String word : words) {
  25.             Node currentNode = node;
  26.             for (int i = 0; i < word.length(); ++i) {
  27.                 char c = word.charAt(i);
  28.                 currentNode.next.putIfAbsent(c, new Node(c));
  29.                 currentNode = currentNode.next.get(c);
  30.             }
  31.             currentNode.leaf = true;
  32.         }
  33.         return node;
  34.     }
  35.  
  36.     public static List<String> findAllConcatenatedWordsInADict(String[] words) {
  37.         Node node = build(words);
  38. //        dfs(node, "");
  39.         Set<String> ans = new HashSet<>();
  40.         for (String word : words) {
  41.             dfs(word, node, node, 0, 0, ans);
  42.         }
  43.         return new ArrayList<>(ans);
  44.     }
  45.  
  46.     static void dfs(String currentWord, Node currentNode, Node root, int pos, int cnt, Set<String> ans) {
  47.         if (pos > currentWord.length() - 1) {
  48.             if (cnt > 1) {
  49.                 ans.add(currentWord);
  50.             }
  51.             return;
  52.         }
  53.         char currentChar = currentWord.charAt(pos);
  54.         if (currentNode.next.containsKey(currentChar)) {
  55.             Node nextNode = currentNode.next.get(currentChar);
  56.             dfs(currentWord, nextNode, root, pos + 1, cnt, ans);
  57.             if (nextNode.leaf) {
  58.                 dfs(currentWord, root, root, pos + 1, cnt + 1, ans);
  59.             }
  60.         }
  61.     }
  62.  
  63.     static void dfs(Node node, String word) {
  64.         if (node.leaf) {
  65.             System.out.println(word + node.c);
  66.         }
  67.         node.next.values().forEach(d -> dfs(d, word + node.c));
  68.     }
  69.  
  70.     public static void main(String[] args) {
  71.         String[] words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
  72.         List<String> allConcatenatedWordsInADict = findAllConcatenatedWordsInADict(words);
  73.         for (String s : allConcatenatedWordsInADict) {
  74.             System.out.println(s);
  75.         }
  76.  
  77.     }
  78. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top