ogv

Untitled

ogv
Oct 22nd, 2019
79
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. ArrayList<Integer> r = new ArrayList<>();
  13. r.add(find.wordIndex);
  14. r.add(i);
  15. result.add(r);
  16. }
  17. }
  18.  
  19. return result;
  20. }
  21.  
  22. class TrieNode {
  23. int wordIndex;
  24. Map<Character, TrieNode> next;
  25.  
  26. public TrieNode() {
  27. next = new HashMap<Character, TrieNode>();
  28. wordIndex = -1;
  29. }
  30.  
  31. public void add(String s, int wordIndex) {
  32. addInt(s, 0, wordIndex);
  33. }
  34.  
  35. private void addInt(String s, int index, int wordIndex) {
  36. if (index >= s.length()) {
  37. this.wordIndex = wordIndex;
  38. }
  39. else {
  40. char c = s.charAt(index);
  41. TrieNode n = getOrAdd(c);
  42. n.addInt(s, index + 1, wordIndex);
  43. }
  44. }
  45.  
  46. private TrieNode getOrAdd(char c) {
  47. TrieNode n = next.get(c);
  48. if (n == null) {
  49. n = new TrieNode();
  50. next.put(c, n);
  51. }
  52. return n;
  53. }
  54.  
  55. public List<FindResult> findBackwards(String s) {
  56. List<FindResult> res = new ArrayList<>();
  57. TrieNode node = this;
  58. for (int i = s.length()-1; i>=0; i--){
  59. char c = s.charAt(i);
  60. node = node.next.get(c);
  61. if (node == null) break;
  62. if (node.wordIndex != -1) res.add(new FindResult(node.wordIndex, i));
  63. }
  64. return res;
  65. }
  66. }
  67.  
  68. class FindResult {
  69. public int strIndex;
  70. public int wordIndex;
  71. public FindResult(int wordIndex, int strIndex){
  72. this.wordIndex = wordIndex;
  73. this.strIndex = strIndex;
  74. }
  75. }
  76. }
RAW Paste Data