提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

Leetcode: Palindrome Pairs

LeetCode Palindrome Pairs
2023-09-11 14:14:07 时间 
 1 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.
 2 
 3 Example 1:
 4 Given words = ["bat", "tab", "cat"]
 5 Return [[0, 1], [1, 0]]
 6 The palindromes are ["battab", "tabbat"]
 7 Example 2:
 8 Given words = ["abcd", "dcba", "lls", "s", "sssll"]
 9 Return [[0, 1], [1, 0], [3, 2], [2, 4]]
10 The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

Naive Solution: Time:  O(n^2*k) with n the total number of words in the "words" array and k the average length of each word: check each combination see if it's palindrome. TLE of course.

 

Better Solution: Time: O(n*k^2)

think of a word A which contains two part, 

1.   A = XX + B,    XX is palindrome, then "B_reverse + XX + B" will make a palindrome, find if B_reverse exists in the the list

2.   A = C + XX ,   then "C + XX + C_reverse" will make a palindrome, find if C_reverse exists in the list,

To ensure quick search, use HashMap 

 

Be careful about duplicate search:  [abcd, dcba],

in first iteration, we look at word abcd, at iteration where sndHalf == "", we add {0,1}

in second iteration, we look at word dcba, at iteration where fstHaf == "", we also add {0, 1}, duplicates

 1 public class Solution {
 2     public List<List<Integer>> palindromePairs(String[] words) {
 3         List<List<Integer>> res = new ArrayList<List<Integer>>();
 4         if (words==null || words.length==0) return res;
 5         Map<String, Integer> map = new HashMap<>();
 6         for (int i=0; i<words.length; i++) {
 7             map.put(words[i], i);
 8         }
 9         for (int i=0; i<words.length; i++) {
10             int len = words[i].length();
11             for (int j=0; j<=words[i].length(); j++) {
12                 String fstHalf = words[i].substring(0, j);
13                 String sndHalf = words[i].substring(j);
14                 
15                 if (isPalindrome(fstHalf)) {
16                     String sndHalfRev = new StringBuffer(sndHalf).reverse().toString();
17                     if (map.containsKey(sndHalfRev) && map.get(sndHalfRev)!=i) { //"aaaa" case
18                         ArrayList<Integer> item = new ArrayList<Integer>();
19                         item.add(map.get(sndHalfRev));
20                         item.add(i);
21                         res.add(new ArrayList<Integer>(item));
22                     }
23                 }
24                 if (isPalindrome(sndHalf)) {
25                     String fstHalfRev = new StringBuffer(fstHalf).reverse().toString();
26                     if (map.containsKey(fstHalfRev) && map.get(fstHalfRev)!=i && sndHalf.length()!=0) {
27                         ArrayList<Integer> item = new ArrayList<Integer>();
28                         item.add(i);
29                         item.add(map.get(fstHalfRev));
30                         res.add(new ArrayList<Integer>(item));
31                     }
32                 }
33             }
34         }
35         return res;
36     }
37     
38     public boolean isPalindrome(String str) {
39         int r = str.length()-1;
40         int l = 0;
41         while (l <= r) {
42             if(str.charAt(l++) != str.charAt(r--)) return false;
43         }
44         return true;
45     }
46 }

 

另有Trie做法未深究https://discuss.leetcode.com/topic/39585/o-n-k-2-java-solution-with-trie-structure-n-total-number-of-words-k-average-length-of-each-word/2

相关文章