# Untitled

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<>();
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) {
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);
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