Data Structre_Trie - xwu36/LeetCode GitHub Wiki
Trie is an efficient information retrieval data structure. Using trie, search complexities can be brought to optimal limit (key length). If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree. Using trie, we can search the key in O(M) time. However the penalty is on trie storage requirements.
Problem:
Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]
Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
Code:
public class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> palindromePairs(String[] words) {
Trie tree = new Trie();
tree.buildTree(words);
int index = -1;
for(int i = 0; i < words.length; i++){
if(words[i].length() == 0)
index = i;
tree.searchNode(words[i], i);
}
if(index >= 0){
for(int i = 0; i < words.length; i++){
if(i != index && isPalindrome(words[i])){
res.add(Arrays.asList(new Integer[]{i, index}));
}
}
}
return res;
}
class Trie{
TrieNode root = new TrieNode();
public void buildTree(String[] words){
for(int i = 0; i < words.length; i++){
TrieNode tmp = root;
String word = words[i];
for(int j = word.length() - 1; j >= 0; j--){
if(!tmp.children.containsKey(word.charAt(j)))
tmp.children.put(word.charAt(j), new TrieNode());
tmp = tmp.children.get(word.charAt(j));
}
tmp.isWord = true;
tmp.word = word;
tmp.index = i;
}
}
public void searchNode(String word, int index){
TrieNode tmp = root;
for(int i = 0; i < word.length(); i++){
if(!tmp.children.containsKey(word.charAt(i)))
return;
tmp = tmp.children.get(word.charAt(i));
if(tmp.isWord && index != tmp.index
&& isPalindrome(word.substring(tmp.word.length(), word.length()))){
res.add(Arrays.asList(new Integer[]{index, tmp.index}));
}
}
getAllChildren(tmp, word, index);
}
public void getAllChildren(TrieNode parent, String word, int index){
for(char key : parent.children.keySet()){
TrieNode cur = parent.children.get(key);
if(cur.isWord && index != cur.index && isPalindrome(cur.word.substring(0, cur.word.length() - word.length())))
res.add(Arrays.asList(new Integer[]{index, cur.index}));
getAllChildren(cur, word, index);
}
}
}
private boolean isPalindrome(String s){
int left = 0;
int right = s.length() - 1;
while(left < right){
if(s.charAt(left) != s.charAt(right))
return false;
left++;
right--;
}
return true;
}
class TrieNode{
public String word;
public boolean isWord;
public int index;
public Map<Character, TrieNode> children;
TrieNode(){
word = "";
isWord = false;
children = new HashMap<Character, TrieNode>();
}
}
}