回文對
給定一組唯一的單詞, 找出所有不同 的索引對(i, j),使得清單中的兩個單詞, words[i] + words[j] ,可拼接成回文串。
示例 1:
輸入: ["abcd","dcba","lls","s","sssll"]
輸出: [[0,1],[1,0],[3,2],[2,4]]
解釋: 可拼接成的回文串為 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2:
輸入: ["bat","tab","cat"]
輸出: [[0,1],[1,0]]
解釋: 可拼接成的回文串為 ["battab","tabbat"]
題解:
可以合成Palindrome Pairs有幾種情況:
1. ["abc", "cba"]
2. ["aabc", "cb"]
3. ["cbaa", "bc"]
要麼有個目前string的reverse過來的string也存在,要麼目前string的左半部分或者右半部分已經是palindrome, 剩下部分有reverse過來的string存在.
先用HashMap把原有string 和對應index儲存。然後對于每一個string拆成left 和 right兩個substring, 若是其中一個substring本身就是palindrom, 就看另一個substring的reverse是不是存在.
當然""也是palindrome, 是以如果左右有""存在, 那就是看left, right本身有沒有對應的reverse存在.
Note: 要注意["abc", "cba"], 一個substring為""的情況隻檢查一遍. 不然先檢查"abc", left = "", right = "abc", 或者right = "", left = "abc", reverse都存在,就會加[0,1], [1,0]. 等再檢查 "cba"時 又會重複加一遍結果. 是以第二個check時要加上right.length() != 0.
Time Complexity: O(n * len), n = words.length, len時word的平均長度.
Space: O(n), regardless res.
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 < 2){
5 return res;
6 }
7
8 HashMap<String, Integer> hm = new HashMap<String, Integer>();
9 for(int i = 0; i<words.length; i++){
10 hm.put(words[i], i);
11 }
12
13 for(int i = 0; i<words.length; i++){
14 for(int j = 0; j<=words[i].length(); j++){ //j是能到word[i].length()的
15 String left = words[i].substring(0, j);
16 String right = words[i].substring(j);
17
18 if(isPalindrome(left)){
19 String reverseRight = new StringBuilder(right).reverse().toString();
20 if(hm.containsKey(reverseRight) && hm.get(reverseRight)!=i){
21 List<Integer> item = new ArrayList<Integer>();
22 item.add(hm.get(reverseRight));
23 item.add(i);
24 res.add(item);
25 }
26 }
27 if(isPalindrome(right)){
28 String reverseLeft = new StringBuilder(left).reverse().toString();
29 if(hm.containsKey(reverseLeft) && hm.get(reverseLeft) != i && right.length()!=0){
30 //Addition check is right.length() != 0
31 //Or will add duplicate results, like ["abc", "cba"]
32 List<Integer> item = new ArrayList<Integer>();
33 item.add(i);
34 item.add(hm.get(reverseLeft));
35 res.add(item);
36 }
37 }
38 }
39 }
40 return res;
41 }
42
43 private boolean isPalindrome(String s){
44 int l = 0;
45 int r = s.length()-1;
46 while(l<=r){
47 if(s.charAt(l++) != s.charAt(r--)){
48 return false;
49 }
50 }
51 return true;
52 }
53 }