[LeetCode 336] Palindrome Paris

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:

Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]] 
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]

Solution:

要求找出回文对，就是两个单词拼起来是个回文字符串

1. 用HashMap来建立reversed word和index的映射
2. 遍历words list，对于遍历到的单词，在HashMap查找是否有对应的翻转后的字符串存在，
   • Note： 注意不能和原字符串的坐标位置相同，因为有可能一个单词翻转后和原单词相等，
   • 现在只是处理了bat和tab的情况，还存在abcd和cba，dcb和abcd这些情况需要考虑
3. 将单词的前一部分如果可以在hash表中找到匹配说明这部分是可以回文的, 如果这个单词剩下的部分也是回文, 那么这两个单词就可以配成回文.
   • For example： abb和ba, 其中ab在HashMap中是以逆序存在的, 即ba, 遍历到abb的时候其前半部分ab可以在HashMap中查到, 并且剩余部分b回文, 因此他们可以构成回文
4. 如果单词的后一部分可以在HashMap中查到, 并且其前一部分是回文, 他们也可以构成匹配.

• For example: 例如aabb和ccbbaa, 其中aabb在HashMap中是以bbaa存在的. 遍历到ccbbaa的时候, 其后一部分bbaa可以在HashMap中查到存在, 并且其前一部分cc是回文, 因此他们也可以构成回文.

特殊情况,

1. 要防止与其本身进行匹配

2. 当存在空串时, 就会复杂一些, 比如["a", ""], 这种情况应该输出[[0, 1] [1, 0]]. 因此空串也应该在作为其前缀和后缀进行检测. 但是这种情况又会引起另外的问题, 例如aabb和bbaa, 当我们将单词划分为左右两部分并且其前半部分为空串或这后半部分为空串时都会匹配, 也就是遍历到aabb时会产出两个匹配, 即aabb作为前缀, 空串作为后缀 和空串作为前缀, aabb作为后缀时. 而遍历到单词bbaa时又会重复匹配一次, 因此我们需要引入另外一个条件, 即在分别判断将当前单词的前一部分作为前缀和后一部分作为后缀的时候, 其前缀和后缀不能同时等于单词本身.

参考https://blog.csdn.net/qq508618087/article/details/51443809

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<> ();
        if (words == null || words.length == 0)
            return result;
        
        //1. a map to store reversed word and its index in words list
        Map<String, Integer> tracker = new HashMap<> ();
        for (int i = 0; i < words.length; i++) {
            String reverse = new StringBuilder (words[i]).reverse ().toString ();
            tracker.put (reverse, i);
        }
        
        //2. scan words list, and try to find pairs by finding matched left partial word in map, and right partial word in map
        for (int i = 0; i < words.length; i++) {
            String currentStr = words[i];
            
            
            // note: must <= length (); otherwise cannot get "" as the last right substring
            for (int wordIndex = 0; wordIndex <= currentStr.length (); wordIndex ++) {
                String left = currentStr.substring (0, wordIndex);
                String right = currentStr.substring (wordIndex, currentStr.length ());
                
                //System.out.println ("left: " + left + " right: " + right);
                
                //handle "abb" and "ba", 
                // when left == "ab" isPalindrome: '
                // left == "ab" can find a match in map (reversed ba), right == "b" isPalindrome
                // the index of left in map shouldn;t be equal to the index of itself, handle match itself
                // eg. "aa", in map, reversed word is it self
                if (isPalindrome (left)) {
                    
                    if (tracker.containsKey (right) && tracker.get (right) != i) {
                        List<Integer> index = new ArrayList<> ();
                        index.add (tracker.get (right));
                        index.add (i);
                        
                        //System.out.println ("1");
                        result.add (index);
                    }
                }
                
                if (isPalindrome (right)) {
                    if (tracker.containsKey (left) &&
                        tracker.get (left) != i &&
                        right.length () != 0) {
                        // right cannot be "", otherwise it will result in duplicate. becasue left can be ""
                        
                        List<Integer> index = new ArrayList<> ();
                        index.add (i);
                        index.add (tracker.get (left));
                        
                        System.out.println ("2");
                        
                        result.add (index);
                    }
                }
            }
        }
        
        return result;
    }
    
    public boolean isPalindrome (String str) {
        int start = 0;
        int end = str.length () - 1;
        
        while (start <= end) {
            if (str.charAt (start++) != str.charAt (end--)) {
                return false;
            }
        }
        
        return true;
    }
}