SHARE
TWEET

Untitled

ogv Oct 22nd, 2019 96 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     public List<List<Integer>> palindromePairs(String[] words) {
  3.         TrieNode trie = new TrieNode();
  4.         for (int i = 0; i < words.length; i++) trie.add(words[i], i);
  5.        
  6.         List<List<Integer>> result = new ArrayList<List<Integer>>();
  7.        
  8.         for (int i = 0; i < words.length; i++) {
  9.             TrieNode n = trie.findBackwards(words[i]);
  10.             if (n != null && n.wordIndex != -1 && n.wordIndex != i) {
  11.                 ArrayList<Integer> r = new ArrayList<>();
  12.                 r.add(n.wordIndex);
  13.                 r.add(i);
  14.                 result.add(r);
  15.             }
  16.         }
  17.                
  18.         return result;
  19.     }
  20.    
  21.     class TrieNode {
  22.         int wordIndex;
  23.         Map<Character, TrieNode> next;
  24.        
  25.         public TrieNode() {
  26.             next = new HashMap<Character, TrieNode>();
  27.             wordIndex = -1;
  28.         }
  29.        
  30.         public void add(String s, int wordIndex) {
  31.             addInt(s, 0, wordIndex);
  32.         }
  33.        
  34.         private void addInt(String s, int index, int wordIndex) {
  35.             if (index >= s.length()) {                
  36.                 this.wordIndex = wordIndex;
  37.             }
  38.             else {
  39.                 char c = s.charAt(index);
  40.                 TrieNode n = getOrAdd(c);
  41.                 n.addInt(s, index +  1, wordIndex);
  42.             }
  43.         }
  44.        
  45.         private TrieNode getOrAdd(char c) {
  46.             TrieNode n = next.get(c);
  47.             if (n == null) {
  48.                 n = new TrieNode();
  49.                 next.put(c, n);
  50.             }
  51.             return n;
  52.         }
  53.        
  54.         public TrieNode findBackwards(String s) {
  55.             return findBackwards(s, s.length() - 1);
  56.         }
  57.        
  58.         private TrieNode findBackwards(String s, int idx) {
  59.             if (idx < 0) return this;
  60.            
  61.             char c = s.charAt(idx);
  62.             TrieNode n = next.get(c);
  63.             if (n == null) return null;
  64.            
  65.             return n.findBackwards(s, idx - 1);
  66.         }
  67.     }
  68. }
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