336. Palindrome Pairs

  • 25.3%

https://leetcode.com/problems/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.

1
2
3
4
Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]
1
2
3
4
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"]

568ms, , April.26th, 2016

Easy to understand AC C++ solution O(n* k^2) using map

Assumption: No duplicated string in the given dictionary

Steps:

  1. Traverse the array, build map. Key is the reversed string, value is index in array (0 based)

  2. Edge case - check if empty string exists. It’s interesting that for given words {“a”, “”}, it’s expected to return two results [0,1] and [1,0]. Since my main logic can cover [0, 1] concatenate(“a”, “”), so as to cover the other situation concatenate(“”, “a”), I need to traverse the words array again, find the palindrome word candidate except “” itself, and add pair(“”, palindrome word) to the final answer.

  3. Main logic part. Partition the word into left and right, and see 1) if there exists a candidate in map equals the left side of current word, and right side of current word is palindrome, so concatenate(current word, candidate) forms a pair: left | right | candidate. 2) same for checking the right side of current word: candidate | left | right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string, int> dict;
vector<vector<int>> ans;
// build dictionary
for(int i = 0; i < words.size(); i++) {
string key = words[i];
reverse(key.begin(), key.end());
dict[key] = i;
}
// edge case: if empty string "" exists, find all palindromes to become pairs ("", self)
if(dict.find("")!=dict.end()){
for(int i = 0; i < words.size(); i++){
if(i == dict[""]) continue;
if(isPalindrome(words[i])) ans.push_back({dict[""], i}); // 1) if self is palindrome, here ans covers concatenate("", self)
}
}

for(int i = 0; i < words.size(); i++) {
for(int j = 0; j < words[i].size(); j++) {
string left = words[i].substr(0, j);
string right = words[i].substr(j, words[i].size() - j);

if(dict.find(left) != dict.end() && isPalindrome(right) && dict[left] != i) {
ans.push_back({i, dict[left]}); // 2) when j = 0, left = "", right = self, so here covers concatenate(self, "")
}

if(dict.find(right) != dict.end() && isPalindrome(left) && dict[right] != i) {
ans.push_back({dict[right], i});
}
}
}

return ans;
}

bool isPalindrome(string str){
int i = 0;
int j = str.size() - 1;

while(i < j) {
if(str[i++] != str[j--]) return false;
}

return true;
}

};

https://discuss.leetcode.com/topic/51771/clean-c-implementation

Clean C++ implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> result;
unordered_map<string, int> dict;
for(int i = 0; i < words.size(); i++) {
dict[words[i]] = i;
}
for(int i = 0; i < words.size(); i++) {
for(int j = 0; j <= words[i].length(); j++) {
//check the suffix word
if(is_palindrome(words[i], j, words[i].size() - 1)) {
/** the suffix word can be null to all the word **/
string suffix = words[i].substr(0, j);
reverse(suffix.begin(), suffix.end());
if(dict.find(suffix) != dict.end() && i != dict[suffix]) {
result.push_back({i, dict[suffix]});
}
}
//check the prefix word
if(j > 0 && is_palindrome(words[i], 0, j - 1)) {
string prefix = words[i].substr(j);
reverse(prefix.begin(), prefix.end());
if(dict.find(prefix) != dict.end() && dict[prefix] != i) {
result.push_back({dict[prefix], i});
}
}
}
}
return result;
}

bool is_palindrome(string& s, int start, int end) {
while(start < end) {
if(s[start++] != s[end--]) {
return false;
}
}
return true;

}
};

https://discuss.leetcode.com/topic/39526/python-solution

572ms, , 134/134, April.26th, 2016

Python solution~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
wordict = {}
res = []
for i in range(len(words)):
wordict[words[i]] = i
for i in range(len(words)):
for j in range(len(words[i])+1):
tmp1 = words[i][:j]
tmp2 = words[i][j:]
if tmp1[::-1] in wordict and wordict[tmp1[::-1]]!=i and tmp2 == tmp2[::-1]:
res.append([i,wordict[tmp1[::-1]]])
if j!=0 and tmp2[::-1] in wordict and wordict[tmp2[::-1]]!=i and tmp1 == tmp1[::-1]:
res.append([wordict[tmp2[::-1]],i])

return res

https://discuss.leetcode.com/topic/39584/accepted-python-solution-with-explanation

Accepted Python Solution With Explanation

The basic idea is to check each word for prefixes (and suffixes) that are themselves palindromes. If you find a prefix that is a valid palindrome, then the suffix reversed can be paired with the word in order to make a palindrome. It’s better explained with an example.

1
words = ["bot", "t", "to"]

Starting with the string “bot”. We start checking all prefixes. If “”, “b”, “bo”, “bot” are themselves palindromes. The empty string and “b” are palindromes. We work with the corresponding suffixes (“bot”, “ot”) and check to see if their reverses (“tob”, “to”) are present in our initial word list. If so (like the word to”to”), we have found a valid pairing where the reversed suffix can be prepended to the current word in order to form “to” + “bot” = “tobot”.

You can do the same thing by checking all suffixes to see if they are palindromes. If so, then finding all reversed prefixes will give you the words that can be appended to the current word to form a palindrome.

The process is then repeated for every word in the list. Note that when considering suffixes, we explicitly leave out the empty string to avoid counting duplicates. That is, if a palindrome can be created by appending an entire other word to the current word, then we will already consider such a palindrome when considering the empty string as prefix for the other word.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def is_palindrome(check):
return check == check[::-1]

words = {word: i for i, word in enumerate(words)}
valid_pals = []
for word, k in words.iteritems():
n = len(word)
for j in range(n+1):
pref = word[:j]
suf = word[j:]
if is_palindrome(pref):
back = suf[::-1]
if back != word and back in words:
valid_pals.append([words[back], k])
if j != n and is_palindrome(suf):
back = pref[::-1]
if back != word and back in words:
valid_pals.append([k, words[back]])
return valid_pals
谢谢你,可爱的朋友。