Java solution using 2 Tries (Prefix Trie + Suffix Trie)


  • 0
    M
    public class Solution {
        private class TrieNode{
    		Map<Character, TrieNode> next;
    		boolean isWord;
    		int index;
    		List<Integer> list;
    		public TrieNode() {
    			next = new HashMap<>();
    			list = new ArrayList<>();
    			isWord = false;
    			index = -1;
    		}
    	}
    	private class Trie {
    		boolean isPrefix;
    		TrieNode root;
    		public Trie(String[] words, boolean isPrefix) {
                root = new TrieNode();
    			this.isPrefix = isPrefix;
    			if (words == null) return;
    			for (int i = 0; i < words.length; ++i) {
    				insert(words[i], i);
    			}
    		}
    		public void insert(String word, int ind) {
    			if (!isPrefix) {
    				word = new StringBuilder(word).reverse().toString();
    			}
    			TrieNode cur = root;
    			for (int i = 0; i < word.length(); ++i) {
    				char c  = word.charAt(i);
    				if (!cur.next.containsKey(c)) cur.next.put(c, new TrieNode());
    				if (isPal(word, i)) cur.list.add(ind);
    				cur = cur.next.get(c);
    			}
    			cur.isWord = true;
    			cur.index = ind;
                cur.list.add(ind);
    		}
    	}
    	private boolean isPal(String word, int start) {
    		int end = word.length() - 1;
    		while (start < end) {
    			if (word.charAt(start++) != word.charAt(end--)) return false;
    		}
    		return true;
    	}
    	private void dfs(TrieNode pre, TrieNode suf, boolean[][] res) {
    		if (pre == null || suf == null) return;
    		if (pre.isWord) {            
    			for (int ind : suf.list) {
                    res[pre.index][ind] = true;
    			}
    		} 
            if (suf.isWord) {
    			for (int ind : pre.list) {
                    res[ind][suf.index] = true;
    			}
    		}
    		for (char c : pre.next.keySet()) {
    			dfs(pre.next.get(c), suf.next.get(c), res);
    		}
    	}
    	public List<List<Integer>> palindromePairs(String[] words) {
    		List<List<Integer>> lists = new ArrayList<>();
    		if (words == null || words.length < 2) return lists;
    		Trie preTrie = new Trie(words, true), sufTrie = new Trie(words, false);
    		boolean[][] res = new boolean[words.length][words.length];
            dfs(preTrie.root, sufTrie.root, res);
            for (int i = 0; i < res.length; ++i) {
                for (int j = 0; j < res[0].length; ++j) {
                    if (i != j && res[i][j]) {
                        List<Integer> list = new ArrayList<>();
                        list.add(i);
                        list.add(j);
                        lists.add(list);
                    }
                }
            }
            return lists;
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.