static class TrieNode {

// 단어 ID를 저장하는 변수

int wordId;

// 트라이의 자식 노드들

TrieNode[] children;

// 팰린드롬인 단어 ID를 목록으로 저장하는 변수

List<Integer> palindromeWordIds;

public TrieNode() {

// 단어 ID의 초깃값은 의미 없는 값으로 선언

wordId = -1;

// 자식 노드는 알파벳의 개수인 최대 26개까지 가능

children = new TrieNode[26];

// 팰린드롬 단어 ID 목록을 빈 값으로 초기화

palindromeWordIds = new ArrayList<>();

}

}

static class Trie {

TrieNode root;

// 클래스 생성시 루트로 빈 트라이 노드 생성

public Trie() {

root = new TrieNode();

}

// 인덱스를 받아서 팰린드롬 여부를 판별하는 메소드

public boolean isPalindrome(String str, int start, int end) {

// 시작 지점이 종료지점보다 앞에 있으면 계속 반복

while (start < end) {

// 시작 지점은 증가하고 종료 지점은 감소하면서 문자가 일치하는지 확인, 한 번이라도 틀리면 false 리턴

if (str.charAt(start++) != str.charAt(end--)) return false;

}

// 한 번도 틀리지 않을 경우 팰린드롬이므로 true 리턴

return true;

}

// 단어 삽입

public void insert(int index, String word) {

// 루트부터 시작

TrieNode cur = root;

// 단어를 뒤집어서 트라이로 저장

for (int i = word.length() - 1; i >= 0; i--) {

// 단어에서 해당 위치의 문자 추출

char c = word.charAt(i);

// 정방향으로 해당 위치까지 팰린드롬인 경우 단어의 인덱스 저장(그림에서 p로 표시)

if (isPalindrome(word, 0, i)) {

cur.palindromeWordIds.add(index);

}

// 해당 문자의 자식 노드가 존재하지 않으면 신규 트라이 노드 생성

// 'a'가 인덱스 0, 'z'는 인덱스 25가 된다.

if (cur.children[c - 'a'] == null) {

cur.children[c - 'a'] = new TrieNode();

}

// 자식 노드를 현재 노드로 교체

cur = cur.children[c - 'a'];

}

// 단어가 완성된 후 단어의 인덱스 저장(그림에서 w로 표시)

cur.wordId = index;

}

// 팰린드롬 여부 판별

public List<List<Integer>> search(int index, String word) {

// 루트부터 시작

TrieNode cur = root;

// 결과 변수

List<List<Integer>> result = new ArrayList<>();

// 단어의 문자를 차례대로 반복하며 처리

for (int j = 0; j < word.length(); j++) {

// (3) 탐색 중에 단어 ID가 있고(그림에서 w), 나머지 문자가 팰린드롬인 경우

if (cur.wordId >= 0 && isPalindrome(word, j, word.length() - 1)) {

result.add(Arrays.asList(new Integer[]{index, cur.wordId}));

}

// 자식 노드가 없으면 더 이상 팰린드롬이 아니므로 지금까지의 결과를 리턴하면서 중단

if (cur.children[word.charAt(j) - 'a'] == null)

return result;

// 자식 노드를 현재 노드로 교체

cur = cur.children[word.charAt(j) - 'a'];

}

// (1) 끝까지 탐색했을 때 단어 ID가 있는 경우(그림에서 w)

if (cur.wordId >= 0 && cur.wordId != index) {

result.add(Arrays.asList(new Integer[]{index, cur.wordId}));

}

// (2) 끝까지 탐색했을 때 팰린드롬 단어 ID가 있는 경우(그림에서 p)

for (int palindromeWordId : cur.palindromeWordIds) {

result.add(Arrays.asList(new Integer[]{index, palindromeWordId}));

}

// 결과 리턴

return result;

}

}

public List<List<Integer>> palindromePairs(String[] words) {

// 트라이 처리 클래스

Trie t = new Trie();

// 결과 리스트 변수

List<List<Integer>> results = new ArrayList<>();

// 단어 목록을 하나씩 트라이에 추가

for (int i = 0; i < words.length; i++) {

t.insert(i, words[i]);

}

// 단어 목록에서 하나씩 팰린드롬 여부를 판별하고 결과에 누적

for (int i = 0; i < words.length; i++) {

results.addAll(t.search(i, words[i]));

}

// 최종 결과 리턴

return results;

}