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


  • 0
    P

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


  • 0
    P

    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));			
    	}
    }
    

    }
    }


  • 0
    P

    This is not linear time


  • 0

    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]);
            }
        }
    }
    
    
    

  • 0
    W

    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.


  • 0

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

  • 1
    K

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


  • 0
    P

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


  • 0
    K

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


  • 0
    B

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


  • 4
    F

    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.


  • 0

    @fx101 said in Given an array of strings, find if two strings concatenate to form a palindrome in linear time.:

    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.


  • 1
    F

    @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):
            self.words.add(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);
        }
    };
    

  • 1

    @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):
            """
            Initialize your data structure here.
            """
            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
    

Log in to reply
 

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