Buttercola: Airbnb: Palindromic pair of a list of strings
Airbnb: Palindromic pair of a list of strings
Given a list of strings, find all the palindromic pairs of the string and output the concatenated palindrome.
e.g. [abc, cba], output is abccba, cbaabc.
e.g. [aabc, cb], output is cbaabc
Understand the problem:
The brute-force solution to this problem is very simple. For each word, we search all the others and see if it can form a palindrome. Assume that the ave. length of each word is m and there are totally n words in the list, the time complexity would be O(n^2 * m).
Solution:
A better solution is for a given word, we put all its possible words which can form a palindrome into a HashMap. Then for another word, if it is in the map, we know that it is a pair which can forma a palindrome. Note that a word can form a palindrome from front and end, e.g. [abc, cba], the palindrome could be either abccba and cbaabc. So we need to maintain two maps and store the candidate words which can be in the front and end.
The key of the map is the candidate words, and the value is the list of the original words.
e.g. [abc, cba], output is abccba, cbaabc.
e.g. [aabc, cb], output is cbaabc
Understand the problem:
The brute-force solution to this problem is very simple. For each word, we search all the others and see if it can form a palindrome. Assume that the ave. length of each word is m and there are totally n words in the list, the time complexity would be O(n^2 * m).
Solution:
A better solution is for a given word, we put all its possible words which can form a palindrome into a HashMap. Then for another word, if it is in the map, we know that it is a pair which can forma a palindrome. Note that a word can form a palindrome from front and end, e.g. [abc, cba], the palindrome could be either abccba and cbaabc. So we need to maintain two maps and store the candidate words which can be in the front and end.
The key of the map is the candidate words, and the value is the list of the original words.
Read full article from Buttercola: Airbnb: Palindromic pair of a list of strings
No comments:
Post a Comment