• 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.

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.

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

Clean C++ implementation

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

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

Python solution~

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.

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.