Leetcode: 336.Palindrome Pairs
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"]
Strategy:
- List of words, needs one layer of looping
- Number of letters in a word is not fixed, needs deep lool into each word, another layer of looping
- The order of compositing a pair, (a, b) or (b, a), needs to be separated as two times
- When looping, the front part is starting from index 0, and the second part must be ending with the index of length of letters
- Either the front or the second part could be searched in the list of words, and the other part should be tested for palindorme
New Solution:
class Solution {
static class Trie{
TrieNode root;
final static int AlphabetSize = 26;
Trie(){
root = new TrieNode(-1);
}
public void add(String word, int id){
TrieNode head = root;
for(int i = word.length()-1;i>=0; i--){
int j = word.charAt(i) -'a';
if(head.dsc[j] == null){
head.dsc[j] = new TrieNode(-1);
}
if(isPalindrome(word,0,i))
head.indices.add(id);//can cover "" string cases. e.g. for string "aaa",root will have its index
head = head.dsc[j];
}
head.indices.add(id);
head.idx = id;
}
public void search(String word,int id, List<List<Integer>> rs){
TrieNode head = root;
for(int i=0; i< word.length(); i++){
if(head.idx!=-1 && isPalindrome(word,i,word.length()-1))
rs.add(Arrays.asList(id,head.idx));
int j = word.charAt(i) - 'a';
if(head.dsc[j] == null)
return ;
head = head.dsc[j];
}
for(int a : head.indices){
if(a!=id)
rs.add(Arrays.asList(id,a));
}
}
private boolean isPalindrome(String str1, int i, int j){
while(i<=j){
if(str1.charAt(i++)!=str1.charAt(j--)){
return false;
}
}
return true;
}
static class TrieNode{
int idx; // -1 means no words ends at this node. i means words[i] ends here
TrieNode[] dsc;
List<Integer> indices;// indices passing through this node
TrieNode(int idx){
this.idx = idx;
dsc = new TrieNode[AlphabetSize];
indices = new LinkedList<>();
}
}
}
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> rs = new LinkedList<>();
Trie dict = new Trie();
for(int i =0; i< words.length; i++)
dict.add(words[i],i);
for(int i = 0; i<words.length; i++)
dict.search(words[i],i,rs);
return rs;
}
}
My Final Solution:
public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> pairs = new ArrayList<List<Integer>>();
if(words == null || words.length == 0) return pairs;
HashMap<String, Integer> map = new HashMap<>();
for(int i = 0; i < words.length; i++) map.put(words[i], i);
for(int i = 0; i < words.length; i++){
for(int j = 0; j <= words[i].length(); j++){ // <= not <
String frontStr = words[i].substring(0, j);
String backStr = words[i].substring(j);
if(isPalindrome(frontStr)){
String backRev = new StringBuilder(backStr).reverse().toString();
if(map.containsKey(backRev) && map.get(backRev) != i){
pairs.add(Arrays.asList(new Integer[]{map.get(backRev), i}));
}
}
if(isPalindrome(backStr) && backStr.length() != 0){ //exam the length for backString is 0 or not
String frontRev = new StringBuilder(frontStr).reverse().toString();
if(map.containsKey(frontRev) && map.get(frontRev) != i){
pairs.add(Arrays.asList(new Integer[]{i,map.get(frontRev)}));
}
}
}
}
return pairs;
}
private boolean isPalindrome(String s) {
for (int i = 0; i < s.length()/2; ++ i) // half of length
if (s.charAt(i) != s.charAt(s.length()-1-i))
return false;
return true;
}
}
Referenced Solutions:
public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> pairs = new LinkedList<>();
if (words == null) return pairs;
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < words.length; ++ i) map.put(words[i], i);
for (int i = 0; i < words.length; ++ i) {
int l = 0, r = 0;
while (l <= r) {
String s = words[i].substring(l, r);
Integer j = map.get(new StringBuilder(s).reverse().toString());
if (j != null && i != j && isPalindrome(words[i].substring(l == 0 ? r : 0, l == 0 ? words[i].length() : l)))
pairs.add(Arrays.asList(l == 0 ? new Integer[]{i, j} : new Integer[]{j, i}));
if (r < words[i].length()) ++r;
else ++l;
}
}
return pairs;
}
private boolean isPalindrome(String s) {
for (int i = 0; i < s.length()/2; ++ i)
if (s.charAt(i) != s.charAt(s.length()-1-i))
return false;
return true;
}
}
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> pairs = new LinkedList<>();
if(words == null) return pairs;
Map<String, Integer> map = new HashMap<>();
for(int i=0; i<words.length; i++) map.put(words[i], i);
for(int index=0; index<words.length; index++){
String cur = words[index];
for(int j=0; j<cur.length(); j++){
String sub = cur.substring(0, j+1);
StringBuilder reverse = new StringBuilder(sub).reverse();
if(map.containsKey(reverse.toString()) && map.get(reverse.toString())!=index && isPalindrome(cur.substring(j+1)))
pairs.add(Arrays.asList(new Integer[]{index, map.get(reverse.toString())}));
}
int j = cur.length() - 1;
for(int i=1; i<cur.length(); i++){
String sub = cur.substring(i, j+1);
StringBuilder reverse = new StringBuilder(sub).reverse();
if(map.containsKey(reverse.toString()) && map.get(reverse.toString())!=index && isPalindrome(cur.substring(0, i)))
pairs.add(Arrays.asList(new Integer[]{map.get(reverse.toString()), index}));
}
}
return pairs;
}
private boolean isPalindrome(String s) {
for (int i = 0; i < s.length()/2; ++ i)
if (s.charAt(i) != s.charAt(s.length()-1-i))
return false;
return true;
}
}
Referenced from
Author：Jeanz
Link：https://www.jianshu.com/p/f08f2afe9681
Best Solution: (140ms)
public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(words == null || words.length == 0) return res;
HashMap<String, Integer> map = new HashMap<>();
for(int i = 0; i < words.length; i++) map.put(words[i], i);
for(int i = 0; i < words.length; i++){
for(int j = 0; j <= words[i].length(); j++){
String str1 = words[i].substring(0, j);
String str2 = words[i].substring(j);
if(isPalindrome(str1)){
String str2rvs = new StringBuilder(str2).reverse().toString();
if(map.containsKey(str2rvs) && map.get(str2rvs) != i){
List<Integer> list = new ArrayList<Integer>();
list.add(map.get(str2rvs));
list.add(i);
res.add(list);
}
}
if(isPalindrome(str2) && str2.length() != 0){
String str1rvs = new StringBuilder(str1).reverse().toString();
if(map.containsKey(str1rvs) && map.get(str1rvs) != i){
List<Integer> list = new ArrayList<Integer>();
list.add(i);
list.add(map.get(str1rvs));
res.add(list);
}
}
}
}
return res;
}
public boolean isPalindrome(String s){
int left = 0, right = s.length() - 1;
while(left < right){
if(s.charAt(left++) != s.charAt(right--)) return false;
}
return true;
}
}
Referenced from
Author: 大米中的大米
Link: https://segmentfault.com/a/1190000008917798
