Airbnb: Palindromic pair of a list of strings

LeetCode 336 - Palindrome Pairs
Buttercola: 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. 

  public List<String> getPalindromicPairs(String[] input) {

    List<String> result = new ArrayList<>();

    if (input == null || input.length < 2) {

      return result;

    }

     

    // Step 1: add all the revsered order of all

    // words into the set

    Map<String, Integer> map = new HashMap<>();

    for (String str : input) {

      String reverseStr = reverse(str);

      if (!map.containsKey(reverseStr)) {

        map.put(reverseStr, 1);

      } else {

        map.put(reverseStr, map.get(reverseStr) + 1);

      }

    }

     

    for (String str : input) {

      // Iterate all prefix

      for (int i = 1; i <= str.length(); i++) {

        String prefix = str.substring(0, i);

        String postfix = str.substring(i);

         

        if (map.containsKey(prefix) && isPalindrome(postfix)) {

          String reversedStr = reverse(prefix);

          if (!prefix.equals(reversedStr) || (prefix.equals(reversedStr) && map.get(prefix) % 2 == 0)) {

            String tmp = str + reverse(prefix);

            result.add(tmp);

          }

        }

      }

       

      // Iterate all postfix

      for (int i = str.length() - 1; i >= 0; i--) {

        String postfix = str.substring(i);

        String prefix = str.substring(0, i);

         

        if (map.containsKey(postfix) && isPalindrome(prefix)) {

          String rePostfix = reverse(postfix);

          if (!postfix.equals(rePostfix) || (postfix.equals(rePostfix) && map.get(postfix) % 2 == 0)) {

           String tmp = reverse(postfix) + str;

           result.add(tmp);

          }

        }

      }

    }

     

    return result;

     

  }

   

  private String reverse(String s) {

    if (s == null || s.length() == 0) {

      return s;

    }

     

    char[] arr = s.toCharArray();

    int lo = 0;

    int hi = arr.length - 1;

     

    while (lo < hi) {

      char temp = arr[lo];

      arr[lo] = arr[hi];

      arr[hi] = temp;

       

      lo++;

      hi--;

    }

     

    return new String(arr);

  }

   

  private boolean isPalindrome(String s) {

    if (s == null || s.length() <= 1) {

      return true;

    }

     

    int lo = 0;

    int hi = s.length() - 1;

     

    while (lo < hi) {

      if (s.charAt(lo) != s.charAt(hi)) {

        return false;

      }

       

      lo++;

      hi--;

    }

     

    return true;

  }

Palindrome Pairs – AlgoBox by dietpepsi

Given a list of unique words. Find all pairs of indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]

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"]

Posts: Google, Google, Airbnb

Put all words in a Set. For each word, get all it’s prefix and suffix. Search for reversed(prefix) and reversed(suffix) in the Set.
If found, check if the rest of the string is a palindrome or not. Time complexity .

    public List<List<Integer>> parlindromePairs(String[] words) {

        List<List<Integer>> ans = new ArrayList<>();

        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < words.length; ++i) map.put(words[i], i);

        for (int k = 0; k < words.length; ++k) {

            String word = words[k];

            int n = word.length();

            for (int i = 0; i < n + 1; ++i) {

                String suffix = new StringBuilder(word.substring(0, i)).reverse().toString();

                String prefix = new StringBuilder(word.substring(i, n)).reverse().toString();

                if (i != 0 && map.containsKey(prefix) && map.get(prefix) != k && isPalindrome(suffix))

                    ans.add(Arrays.asList(map.get(prefix), k));

                if (map.containsKey(suffix) && map.get(suffix) != k && isPalindrome(prefix))

                    ans.add(Arrays.asList(k, map.get(suffix)));

            }

        }

        return ans;

    }

    public boolean isPalindrome(String word) {

        for (int i = 0; i < word.length() / 2; ++i)

            if (word.charAt(i) != word.charAt(word.length() - i - 1)) return false;

        return true;

    }

Method 2

1. Preprocess all words using Manacher’s Algorithm and save the results. The step is O(nk).
2. Build a Trie of all words. O(nk).
3. For each word search reversed word in the trie, if found partial match, use the preprocess results to check if the rest of the string is a palindrome in O(1). The step is O(nk).
4. Build a Trie of all reversed words. O(nk).
5. For each word search it in the reversed Trie, if found partial match, use the preprocess results to check if the rest of the string is a palindrome in O(1). The step is O(nk).

Total time complexity is .

Read full article from Buttercola: Airbnb: Palindromic pair of a list of strings