# Given an array of strings, find if two strings concatenate to form a palindrome in linear time.

• given array = {"cat","tac", "rac","car,"ta","abc"}

• public class Test {
private static String[] myarray = {"cat",
"tac",
"rac",
"car",
"ta",
"abc"};

``````private static boolean isPalendrome(String str){
if(str!=null){
if(str.length() ==1 || str.length() == 0){
return true;
}else{
if(str.charAt(0)==str.charAt(str.length()-1))
return isPalendrome(str.substring(1, str.length()-1));
}
}
return false;
}

public static void main(String[] args) {

for(int i = 0; i < Test.myarray.length-1; i++)	{
String Str = null;
for(int j=i+1; j<Test.myarray.length;j++){
Str = Test.myarray[i]+Test.myarray[j];
System.out.println(Str+" is Palindrome -->"+Test.isPalendrome(Str));
}
}
``````

}
}

• This is not linear time

• Java Solution

``````import java.io.*;
import java.util.*;

class Solution {

private ArrayList<String> findPalindromePairs(String[] input) {
ArrayList<String> list = new ArrayList<>();

if(null == input) {
return list;
}

int len = input.length;
if(len <= 1) {
return list;
}

HashMap<String, Integer> map = new HashMap<>();
int count = 0;

for(String str : input) {
count = 0;
if(map.containsKey(str)) {
count = map.get(str);
}

map.put(str, ++count);
}

String rev = "";
for(String str : input) {
rev = new StringBuilder(str).reverse().toString();

if(map.containsKey(rev)) {
count = map.get(rev);

if(count > 0) {
map.put(str, --count);
map.put(rev, --count);

list.add(str + " : " + rev);
}
}
}

return list;

}

public static void main(String[] args) {
Solution obj = new Solution();
String input[] = {"cat","tac", "rac","car", "ta","abc"};

ArrayList<String> output = obj.findPalindromePairs(input);

for(String palPair : output) {
String pair[] = palPair.split(" : ");

System.out.println(pair[0] + "\t" + " : " + "\t" + pair[1]);
}
}
}

``````

• I think it is correct for this array, but the logic has some problems, if the array has atb, then yours wont return atb, ta , but atbta is palindrome.

• @wwsskkaa Thanks for letting me know. I didn't checked this case.

Probably this will fix the issue. I didn't tested it though

``````rev = new StringBuilder(str).reverse().toString();
String pStr = rev.substring(1, rev.length());

if(map.containsKey(rev) || (rev.length()%2 !=0 &&  map.containsKey(pStr)) {
// handle the case where rev is of odd length and map contains the pStr
...
``````

• Actually this is pretty easy.

Let's say I have an array ['cat', 'tac', 'car', 'rac', 'abc']

Turn that array into a hashtable. Do a for each loop through the array.

Let's say I have cat, the letters needed would be tac. Since now I know what I need, I can just do a look up on the hashmap to see if tac exists. If it exists, concat those two and remove from the array. Rinse and repeat.

The speed of this is O(n * 1) which is just O(n).

• @kngu9 Sure but how would this logic handle the case stated by @wwsskkaa ?

• @praveen47 Oh, I didn't see his caveat.

Well what we can do at that point is trim the first character of the word we are searching until there's nothing left or we found the palindrome.

So let A = ['abc', 'tb', 'ac', 'ba']

Since we now to achieve a palindrome of abc we need 'cba'.
We then look up the hashmap for 'cba', if this does not exist we then trim the first character so that we are looking for 'ba'.

This would be an O(nlogn) solution.

Edit: I don't believe there is a linear solution to this if we take @wwsskkaa 's issue in to this.

• @ramanpreetSinghKhinda
Some cases need to be checked. if the array has aaaa and a. Yours won't return this pair. aaaaa is palindrome.

• Palindromes can be even (eg; "abccba") where one half is a reflection of another or they can be odd (eg; "abcdcba") where one half is equal to the other half separated by a middle element.

The tricky part is what if we have "ab" come before "ccba" in the case of an even palindrome? Or if we have "actb" come before "tca" in the case of an odd palindrome (per @wwsskkaa)?

The trick is we have to find an O(N) or better way to search for a complement among our options. The solution is a trie.

1. We first populate a trie with our strings. This is an O(N) process (because the O(N) loop dominates the O(max(keylen)) term).

2. Next, we iterate through our array of strings, and reverse each one. We'll call each reversed string rev(s) Now we search for the reversed string in the trie.

Option 1: The reversed string doesn't exist in the trie. We move on.
Option 2: We find the reversed string in the trie but we're not at a leaf node. Then for each candidate remaining in the trie, we must check to see if it's a palindrome. Worst case, this is an O(N) step if we have to check each one... but then we'd be done. If we find one, we're done too (we just need to check IF a palindrome exists).

Let's assume option 2 didn't pan out. Then we remove that string from the trie (nothing can match against it). Then we move onto the next string per step 2.

This should be O(N) since we have a bunch of smaller operations dominated by the big loop O(N). When we do have to iterate more in the inner loop (through the different matches in option 2) then the outer loop has less iterations. The sum of the iterations is at most N. However, this approach is much too complex for an interview, IMO.

• However, this approach is much too complex for an interview, IMO.

Can't agree more. And If you have bugs or failed to compile(whatever reason, like wrong variable name, missing ; }...etc) YOU FAILED the whole interview.

• @new2500 actually this is definitely doable in an interview if you practice making a trie. I've now practiced writing one out so I can bang one out and use it in problems. Here are python and C++ versions. These tries have hash tables built in for quick existence checks if needed. Otherwise, the most common functionality is to search for matches given a prefix (represented here by the `match` functions).

``````class Trie(object):
def __init__(self):
self.root = {}
self.words = set()

#inserts a word into the trie
def insert(self,word):
cur = self.root
for c in word:
cur = cur.get(c,{})

#check if full match exists
def exists(self,word):
return word in self.words

#helper recursive function retrieves list of matches for a given prefix and start
def match_helper(self, start, prefix):
matches = []
if prefix in self.words:
matches.append(prefix)
if start:
for char in start:
matches += self.match_helper(start[char], prefix+char)
return matches

#returns all words matching a given prefix
def match(self,prefix):
#traverse to end of prefix
cur = self.root
for char in prefix:
if char not in cur:
return [] #not in trie
cur = cur[char]
matches = self.match_helper(cur,prefix)
return matches
``````

And here's a C++ version:

``````struct TrieNode {
char val;
unordered_map<char,TrieNode*> children;

TrieNode(char c){val = c;}
~TrieNode() {
for (auto c : children) {
delete children[c.first];
}
}
bool has(char c){
return children.count(c) > 0;
}
};

class Trie {
unordered_set<string> words;
TrieNode* root;

public:
Trie() {
root = new TrieNode('\0');
}
~Trie() {
delete root;
}

void insert(string word){
words.insert(word);

TrieNode* cur = root;
for (auto c : word) {
if (!cur->has(c))
cur->children[c] = new TrieNode(c);
cur = cur->children[c];
}
}

vector<string> match_helper(string prefix, TrieNode* start) {
vector<string> matches;
if (words.count(prefix))
matches.push_back(prefix);
if (start) {
for (auto c : start->children) {
auto submatches = match_helper(prefix+c.first,start->children[c.first]);
matches.reserve(matches.size()+submatches.size());
matches.insert(matches.end(),submatches.begin(),submatches.end());
}
}
return matches;
}

vector<string> match(string prefix) {
vector<string> matches;
TrieNode* cur = root;
for (auto c : prefix) {
if (!cur->children.count(c)) return matches; //no match
cur = cur->children[c];
}
return match_helper(prefix,cur);
}
};
``````

• @fx101 You can do away with the `words` set in your `Trie` class if you append a terminating character to the last character node of the word. Here is my `Trie` implementation for LeetCode #208 which does what I just described.

``````class Trie(object):

def __init__(self):
"""
"""
self.d = {}

def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
curr = self.d
for char in word:
if char not in curr:
curr[char] = {}
curr = curr[char]
curr['#'] = True

def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
curr = self.d
for char in word:
if char in curr:
curr = curr[char]
else:
return False
return '#' in curr

def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
curr = self.d
for char in prefix:
if char in curr:
curr = curr[char]
else:
return False
return True
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.