[刷题防痴呆] 0336 - 回文对 (Palindrome P

题目地址

https://leetcode.com/problems/palindrome-pairs/description/

题目描述

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:

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

思路

• hash. 把每个word和index存到hashmap.
• 然后对于每一个word, split为str1和str2, 检查str1和str2是不是回文.
• 如果str1是回文, str1作为middle, str2作为suffix, str2的reverse作为prefix, 在hashmap中找, 找到加入res.
• 如果str2是回文, str2作为middle, str1作为prefix, str1的reverse作为suffix, 在hashmap中找, 找到加入res.

关键点

• 注意, 对于str1和str2的检查, 有一个需要检查length不为0, 这样是防止str1和str2本身都在word里, 加两遍.

代码

• 语言支持：Java

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        if (words == null || words.length == 0) {
            return result;
        }
        
        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, words[i].length());
                
                if (isPalindrome(str1)) {
                    String reversedStr2 = new StringBuffer(str2).reverse().toString();
                    if (map.containsKey(reversedStr2) && map.get(reversedStr2) != i && str1.length() != 0) {
                        List<Integer> pair = new ArrayList<>();
                        pair.add(map.get(reversedStr2));
                        pair.add(i);
                        result.add(pair);
                    }
                }
                
                if (isPalindrome(str2)) {
                    String reversedStr1 = new StringBuffer(str1).reverse().toString();
                    if (map.containsKey(reversedStr1) && map.get(reversedStr1) != i) {
                        List<Integer> pair = new ArrayList<>();
                        pair.add(i);
                        pair.add(map.get(reversedStr1));
                        result.add(pair);
                    }
                }
            }
        }
        
        return result;
    }
    
    private boolean isPalindrome(String s) {
        int l = 0;
        int r = s.length() - 1;
        while (l <= r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        
        return true;
    }
}