【LeetCode】Palindrome Pairs(336)

简介:   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.

1. Description


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


2. Answer  


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;
        }
        //build the map save the key-val pairs: String - idx
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < words.length; i++){
            map.put(words[i], i);
        }
        //special cases: "" can be combine with any palindrome string
        if(map.containsKey("")) {
            int blankIdx = map.get("");
            for(int i = 0; i < words.length; i++) {
                if(isPalindrome(words[i])) {
                    if(i == blankIdx) 
                        continue;
                    res.add(Arrays.asList(blankIdx, i));
                    res.add(Arrays.asList(i, blankIdx));
                }
            }
        }
        //find all string and reverse string pairs
        for(int i = 0; i < words.length; i++) {
            String cur_r = reverseStr(words[i]);
            if(map.containsKey(cur_r)) {
              int found = map.get(cur_r);
              if(found == i) continue;
              res.add(Arrays.asList(i, found));
           }
        }
        //find the pair s1, s2 that 
        //case1 : s1[0:cut] is palindrome and s1[cut+1:] = reverse(s2) => (s2, s1)
        //case2 : s1[cut+1:] is palindrome and s1[0:cut] = reverse(s2) => (s1, s2)
        for(int i = 0; i < words.length; i++) {
            String cur = words[i];
            for(int cut = 1; cut < cur.length(); cut++) {
                if(isPalindrome(cur.substring(0, cut))) {
                    String cut_r = reverseStr(cur.substring(cut));
                    if(map.containsKey(cut_r)) {
                        int found = map.get(cut_r);
                        if(found == i) continue;
                        res.add(Arrays.asList(found, i));
                    }
                }
                if(isPalindrome(cur.substring(cut))) {
                    String cut_r = reverseStr(cur.substring(0, cut));
                    if(map.containsKey(cut_r)){
                        int found = map.get(cut_r);
                        if(found == i) continue;
                        res.add(Arrays.asList(i, found));
                    }
                }
            }
        }   
        return res;
    }
    public String reverseStr(String str) {
        StringBuilder sb = new StringBuilder(str);
        return sb.reverse().toString();
    }
    public boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;
        while(i <= j){
            if(s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
     return true;
    } 
}
目录
相关文章
Leetcode 24.Swap Nodes in Pairs
 给你一个链表,交换相邻两个节点,例如给你 1->2->3->4,输出2->1->4->3。   我代码里在head之前新增了一个节点newhead,其实是为了少写一些判断head的代码。
40 0
LeetCode 409. Longest Palindrome
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
74 0
LeetCode 409. Longest Palindrome
|
索引
LeetCode 336. Palindrome Pairs
给定一组唯一的单词, 找出所有不同 的索引对(i, j),使得列表中的两个单词, words[i] + words[j] ,可拼接成回文串。
137 0
LeetCode 336. Palindrome Pairs
|
算法 索引
LeetCode 214. Shortest Palindrome
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
90 0
LeetCode 214. Shortest Palindrome
|
canal
LeetCode 125. Valid Palindrome
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
92 0
LeetCode 125. Valid Palindrome
LeetCode 234. 回文链表 Palindrome Linked List
LeetCode 234. 回文链表 Palindrome Linked List
Leetcode-Easy 234. Palindrome Linked List
Leetcode-Easy 234. Palindrome Linked List
58 0
Leetcode-Easy 234. Palindrome Linked List
LeetCode之Palindrome Number(回文数)
LeetCode之Palindrome Number(回文数)
71 0
|
Java Python
LeetCode 234:回文链表 Palindrome Linked List
​请判断一个链表是否为回文链表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题? Follow up:Could you do it in O(n) time and O(1) space? 解题思路: 首先是寻找链表中间节点,这个可以用快慢指针来解决,快指针速度为2,慢指针速度为1,快指针遍历完链表时,慢指针刚好走到中间节点(相对)。
690 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行