336. Palindrome Pairs
Given a list ofuniquewords, find all pairs ofdistinctindices(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: Input: ["abcd","dcba","lls","s","sssll"] Output: [[0,1],[1,0],[3,2],[2,4]] Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"] ["abcd","dcba","lls","s","sssll"] [[0,1],[1,0],[3,2],[2,4]] ["abcd", "dcba " ,"lls" , "s"," sssll"] 0 1。 2。 3。 4。 0, 1 ["abcd", "dcba [1,0] dcba abcd", 3,2 "s", ,"lls 2,4 lls sssll Solution 1 : dfs (brute force solution ). TLE . Passed 100/ 134 tests But not efficient for long strings , probably need to optimize the checkPalindrome function class Solution { public List<List<Integer>> palindromePairs(String[] words) { List<List<Integer>> res = new ArrayList<>(); List<Integer> tmp = new ArrayList<>(); dfs(res, tmp, words); return res; } private void dfs(List<List<Integer>> res, List<Integer> tmp, String[] words){ // base case if(tmp.size() == 2){ if(checkPalindrome(tmp, words)){ res.add(new ArrayList<>(tmp)); } return; } // dfs if(tmp.size() == 0){ for(int i = 0; i < words.length; i++){ tmp.add(i); dfs(res, tmp, words); // backtrack tmp.remove(tmp.size() - 1); } }else{ for(int i = 0; i < words.length; i++){ if(tmp.get(0) != i){ tmp.add(i); dfs(res, tmp, words); // backtrack tmp.remove(tmp.size() - 1); } } } } private boolean checkPalindrome(List<Integer> tmp, String[] words){ String first = words[tmp.get(0)]; String second = words[tmp.get(1)]; String newString = first + second; int i = 0; int j = newString.length() - 1; while(i < j){ if(newString.charAt(i) != newString.charAt(j)){ return false; } i++; j--; } return true; } } // bug (idea is same as sol 1 ) class Solution { public List<List<Integer>> palindromePairs(String[] words) { List<List<Integer>> res = new ArrayList<>(); List<Integer> tmp = new ArrayList<>(); dfs(res, tmp, words); return res; } private void dfs(List<List<Integer>> res, List<Integer> tmp, String[] words){ // base case if(tmp.size() == 2){ if(checkPalindrome(tmp, words)){ res.add(new ArrayList<>(tmp)); } return; } // dfs if(tmp.size() == 0){ for(int i = 0; i < words.length; i++){ tmp.add(i); dfs(res, tmp, words); // backtrack tmp.remove(tmp.size() - 1); } }else{ for(int i = 0; i < words.length; i++){ if(tmp.get(0) != i){ tmp.add(i); dfs(res, tmp, words); // backtrack tmp.remove(tmp.size() - 1); } } } } private boolean checkPalindrome(List<Integer> tmp, String[] words){ String first = words[tmp.get(0)]; String second = words[tmp.get(1)]; int minLen = Math.min(first.length(), second.length()); for(int i = 0; i < minLen; i++){ if(first.charAt(i) != second.charAt(i)){ return false; } } String restWord = first.length() < second.length() ? new String(second) : new String(first); // string a = string b, is it okay ? int i = 0; int j = restWord.length() - minLen - 1; while(i < j){ if(restWord.charAt(i) != restWord.charAt(j)){ return false; }else{ i++; j--; } } return true; } } // solution 2 : use trie Why can you use trie to make it better ? Write down the thins to optimize , from bf to this better solution , https://leetcode.com/problems/palindrome-pairs/discuss/79195/O(n-*-k2)-java-solution-with-Trie-structure Efficient method It can be done in an efficient manner by using the Trie data structure. The idea is to maintain a Trie of the reverse of all words. 1) Create an empty Trie. 2) Do following for every word:- a) Insert reverse of current word. b) Also store up to which index it is a palindrome. 3) Traverse list of words again and do following for every word. a) If it is available in Trie then return true b) If it is partially available Check the remaining word is palindrome or not If yes then return true that means a pair forms a palindrome. Note: Position upto which the word is palindrome is stored because of these type of cases. // solution 3: use HashMap Why can you use HashMap can make it better ? https://blog.csdn.net/qq508618087/article/details/51443809 https://www.jianshu.com/p/fcde442da61b优质内容筛选与推荐>>