Palindrome Pairs

Leave a comment

February 13, 2017 by oneOokay

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"]


HashMap和Trie:

我的脑子很不适应这个string同时正反思考的pattern…

总的来说:要identify出这些pattern:

  1. 当其中的一个String是””的时候,它可以和任何本身是Palindrome的String组成pair
  2. 当word1和word2就是彼此的Palindrome的时候,word1和word2组成pair
  3. 当word1的前半部分[0:cut](s1)为一个valid Palindrome,它的后半部分[cut + 1: end] (s2)reverse之后,存在一个word2和它相同:那么所组成的Palindrome就是word2|s1|s2,此时word1和word2组成pair
  4. 当word1的后半部分[cut:end](s1)为一个valid Palindrome,它的前半部分[0:cut-1](s2)reverse之后,存在一个word2和它相同:那么所组成的Palindrome就是s2|s1|word2,此时word1和word2组成pair
  • 翻转一个string: StringBuilder sb = new StringBuilder(str).reverse().toString()
  • 把多个T组成一个List: List l = new Arrays.asList(t1,t2,…,tn);
  • s.substring(0,0): 返回 “”
  • s.substring(endIndex): 返回 “”,(不会throw error)
  • s.substring(0, endIndex + 1) :返回””,不会throw error
  • s.substring(endIndex + 1, endIndex + 1): 返回””,不会throw error,
  • s.substring(endIndex + 2): throw error

所以这里就引入了map,写的时候就是要看如何把这四种情况结合在一起写还要避免得到重复结果:

public List palindromePairs(String[] words) {
        List res = new ArrayList<>();
        if (words == null || words.length < 2) return res;
        
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i ++){ //create the map
            map.put(words[i], i);
        }
        String s1 = "";
        String s2 = "";
        String rev = "";
        int index = 0;
        for (int i = 0; i < words.length; i ++){
            for(int j = 0; j <= words[i].length(); j ++){
//s1:""/s2:word -> s1:word/s2:"" word = abc/aba
//s1:""/s2:word=>
//isPalindrome(s1)为true(s1为""):可以找到s2的reverse形成pair["cba","abc"*]
//isPalindrome(s2):如果word本身为一个Palindrome的话,可以找到pair["aba"*,""]
//s1:word/s2:""=>
//isPalindrome(s1)为true(word本身为一个Palindrome),可以找到pair["","aba"*]
//isPalindrome(s2):s2为""不处理.如果处理的话:那么会加入pair["abc"*,"cba"]
//那么当word变成"cba"的时候就会重复添加两个pair
                s1 = words[i].substring(0, j);
                s2 = words[i].substring(j);
                //处理了:case3和case2的一对,以及case1的["",Palindrome]
                if (isPalindrome(s1)){
                    rev = new StringBuilder(s2).reverse().toString();
                    if (map.containsKey(rev)){
                        index = map.get(rev);
                        if (index != i)
                            res.add(Arrays.asList(index, i));
                    }
                }
                //处理了:case 4和 case2中的另外一对,以及case1的[Palindrome,""]
                if (!s2.isEmpty() && isPalindrome(s2)){
                    rev = new StringBuilder(s1).reverse().toString();
                    if (map.containsKey(rev)){
                        index = map.get(rev);
                        if (index != i)
                            res.add(Arrays.asList(i, index));
                    }
                }
            }
        }
        return res;
    }
    
    public boolean isPalindrome(String word){
        if (word == "") return true;
        int start = 0; 
        int end = word.length() - 1;
        while (start < end){
            if (word.charAt(start) != word.charAt(end)) return false;
            start ++;
            end --;
        }
        return true;
    }

Trie…理解起来还挺难的

http://www.allenlipeng47.com/blog/index.php/2016/03/15/palindrome-pairs/

建立一个Trie: 按每个string reverse的顺序建立

  • 其中每一条从root走下来的路线都是words里面的一个词的reverse
  • 每个节点如果存在一个完整的词的话,index为词的index,否则为-1
  • 每个节点有一个List,里头放index,代表从这个节点以下(不包含该点)继续走形成的substring是一个Palindrome. list里面的index就是满足条件的word[index]
  • 如果存在””,那么root的index就不会为-1
  • 如果存在本身为Palindrome的词,那么root的list也就不会为空.该Palindrome的词的index会加在root的list里

一个比较好用的例子是words:[xyxcba, abc, “,xcba, cba, aba]

搜索Trie:

读入每个word,按照正序遍历word同时在trie里面查找,也就是在查找以word prefix reverse为prefix的词是否存在.

  • 如果node == null,说明不存在,返回
  • 如果找到了一个node.index不为-1且不等于当前word的index,那么如果当前word剩余的部分是一个Palindrome的话,就成为了一个满足条件的pair.而且这里能找出[Palindrome,””]
  • 遍历完当前的词,当前的node.index不为-1切不等于当前word的index,说明找到了一个[abc,cba]
  • 最终如果当前node的list不为空的话,也能找到pair了.而且这里能够找到[“”,Palindrome]
public class Solution {
 public List<List<Integer>> palindromePairs(String[] words) {
 List<List<Integer>> res = new ArrayList<>();
 if (words == null || words.length < 2) return res;
 TrieNode root = new TrieNode();
 for(int i = 0; i < words.length; i ++){
 buildTrie(root, words[i], i);}
 
 for (int i = 0; i < words.length; i ++){
 searchTrie(root, words[i], i, res);}
 return res;
 }
 
 public void searchTrie(TrieNode root, String s, int index, List<List<Integer>> res){
 TrieNode node = root;
 //读入一个String, 按正常顺序在trie里面开始查找:
 //相当于:找是否存在以该string的reverse开始的词
 //当s==""时:并不会进入这个for loop
 for (int i = 0; i < s.length(); i ++){
 //找到了一个词c(非当前词s),它的reverse是s的prefix的一部分
 //那么,如果当s剩下的那部分也是Palindrome的话就能够构成s|c为Palindrome
 //特殊情况:这里能够找出pair:[Palindrome,""]
 //这里是由root开始的,所以传入i
 if (node.index != -1 && node.index != index && 
isPalindrome(s, i, s.length() -1)){ 
 res.add(Arrays.asList(index, node.index));
 }
 node = node.next[s.charAt(i) - 'a'];
 if (node == null) return;
//不存在以s的一部分prefix reverse为prefix的词,返回.
 }
 //结束了当前词的循环,停在了最后一个node上,这里可以取得["abc", "cba"]
 if (node.index != -1 && node.index != index){
 res.add(Arrays.asList(index, node.index));
 }
 //特殊情况:当s==""时,这里取得["", Palindrome]
 for (int k : node.list){
 if (k != index){
 res.add(Arrays.asList(index, k));
 }
 }
 }
 
 public void buildTrie(TrieNode root, String s, int index){
 TrieNode node = root;
 for (int i = s.length() - 1; i >= 0; i --){
//把一个词按它的reverse order来build Trie
 int trieIndex = s.charAt(i) - 'a';
 if (node.next[trieIndex] == null)
 node.next[trieIndex] = new TrieNode();
 if (isPalindrome(s, 0, i))
//此时还是在i的前一个节点上,判断从0到i是否是一个palindrome
 //当我们进行search的时候希望在当前点的时候就能够知道再往下走是否是一个palindrome
 //所以"往下走"也就是[0,i]这个substring
 //而且当s本身就是一个Palindrome的时候,就会在root的list里面加上它的index
 node.list.add(index);
 node = node.next[trieIndex];
 }
 //当s == ""的时候,node为root,root的index就为""的index
 node.index = index;
 }
 
 class TrieNode{
 int index;
 TrieNode[] next;
 List<Integer> list;
 public TrieNode(){
 index = -1;
 next = new TrieNode[26];
 list = new ArrayList<Integer>();
 }
 }
 
 public boolean isPalindrome(String s, int start, int end){
 while (start < end){
 if (s.charAt(start) != s.charAt(end)) return false;
 start ++;
 end --;
 }
 return true;
 }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: