SHARE
TWEET

Untitled

ogv Oct 22nd, 2019 76 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.             List<FindResult> finds = trie.findBackwards(words[i]);
  10.             for (FindResult find: finds) {
  11.                 if (find.wordIndex == i) continue;
  12.                 if (!isPali(words[i], find.strIndex)) continue;
  13.                 ArrayList<Integer> r = new ArrayList<>();
  14.                 r.add(find.wordIndex);
  15.                 r.add(i);
  16.                 result.add(r);
  17.             }
  18.         }
  19.                
  20.         return result;
  21.     }
  22.    
  23.     private boolean isPali(String s, int to){
  24.         System.out.println(s + " " + to);
  25.         int l = 0;
  26.         int r = to - 1;
  27.         while (l < r)
  28.             if (s.charAt(l++) != s.charAt(r--)) return false;
  29.        
  30.         return true;
  31.     }
  32.    
  33.     class TrieNode {
  34.         int wordIndex;
  35.         Map<Character, TrieNode> next;
  36.        
  37.         public TrieNode() {
  38.             next = new HashMap<Character, TrieNode>();
  39.             wordIndex = -1;
  40.         }
  41.        
  42.         public void add(String s, int wordIndex) {
  43.             addInt(s, 0, wordIndex);
  44.         }
  45.        
  46.         private void addInt(String s, int index, int wordIndex) {
  47.             if (index >= s.length()) {                
  48.                 this.wordIndex = wordIndex;
  49.             }
  50.             else {
  51.                 char c = s.charAt(index);
  52.                 TrieNode n = getOrAdd(c);
  53.                 n.addInt(s, index +  1, wordIndex);
  54.             }
  55.         }
  56.        
  57.         private TrieNode getOrAdd(char c) {
  58.             TrieNode n = next.get(c);
  59.             if (n == null) {
  60.                 n = new TrieNode();
  61.                 next.put(c, n);
  62.             }
  63.             return n;
  64.         }
  65.        
  66.         public List<FindResult> findBackwards(String s) {
  67.             List<FindResult> res = new ArrayList<>();
  68.             TrieNode node = this;
  69.             for (int i = s.length()-1; i>=0; i--){
  70.                 char c = s.charAt(i);
  71.                 node = node.next.get(c);
  72.                 if (node == null) break;
  73.                 if (node.wordIndex != -1) res.add(new FindResult(node.wordIndex, i));
  74.             }
  75.             return res;
  76.         }
  77.     }
  78.    
  79.     class FindResult {
  80.         public int strIndex;
  81.         public int wordIndex;
  82.         public FindResult(int wordIndex, int strIndex){
  83.             this.wordIndex = wordIndex;
  84.             this.strIndex = strIndex;
  85.         }
  86.     }
  87. }
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