# [LeetCode] 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:
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"]

# 解题思路

//Time Limit Exceeded
public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> indices = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words.length; j++) {
if (j == i) {
continue;
} else {
String temp = words[i] + words[j];
if (isPalindrome(temp)) {
List<Integer> list = new ArrayList<>();
}
}
}
}
return indices;
}

private boolean isPalindrome(String word) {
for (int i = 0, j = word.length() - 1; i < j; i++, j--) {
if (word.charAt(i) != word.charAt(j)) {
return false;
}
}
return true;
}
}

1. 对于空字符串，如果数组中有回文字符串，则将空字符串与回文字符串进行组合。
2. 对于非空字符串，将其进行拆分，如果其中一段为回文，并且数组中可以找到另一段的逆序字符串，则说明可以组合为回文。
例如：”sssll” = “ss” + “sll”，而且数组中存在”lls”，因此组合”lls”和”sssll”。

# 实现代码

//Runtime: 247 ms
public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < words.length; i++) {
map.put(words[i], i);
}

List<List<Integer>> indices = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
if (words[i].length() == 0) {
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (isPalindrome(entry.getKey())) {
}
}
}

for (int j = 0; j < words[i].length(); j++) {
String front = words[i].substring(0, j);
String back = words[i].substring(j, words[i].length());
String rfront = reverse(front);
String rback = reverse(back);
if (isPalindrome(front) && map.containsKey(rback)) {
}
if (isPalindrome(back) && map.containsKey(rfront)) {
}
}
}
return indices;
}

private void addAll(List<List<Integer>> indices, int a, int b) {
if (a == b) {
return;
}
List<Integer> list = new ArrayList<>();
}

private String reverse(String word) {
return new StringBuilder(word).reverse().toString();
}

private boolean isPalindrome(String word) {
for (int i = 0, j = word.length() - 1; i < j; i++, j--) {
if (word.charAt(i) != word.charAt(j)) {
return false;
}
}
return true;
}
}

|
11月前
|
Python
LeetCode 234. 回文链表 Palindrome Linked List
LeetCode 234. 回文链表 Palindrome Linked List
37 0
|
11月前
LeetCode 409. Longest Palindrome

49 0
|
11月前
|

LeetCode 336. Palindrome Pairs

71 0
|
11月前
|

LeetCode 214. Shortest Palindrome

41 0
|
11月前
|
canal
LeetCode 125. Valid Palindrome

55 0
【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.
70 0
LeetCode之Palindrome Number（回文数）
LeetCode之Palindrome Number（回文数）
52 0
|
Java Python