Palindrome Pairs

#Airbnb #Medium

Question

Given a list of unique words, find palindromes that can be formed by concatenating two words.

Explanation Video

Explain how to approach the question and coding explanation as well.

Solution

In order for two strings with the same length to form a palindrome, one string needs to be the reversed string of the other one. Using this observation, reverse each input string and save it in a set. Then, re-iterate through the input strings and check whether the string exists in the set.

Q. How about words w/ different length forming a palindrome? Take one letter from the back/front at a time and see if the taken out letters form a palindrome and the remaining letters has a reversed string in the set.

  // Check whether the given string is a palindrome or not.
  private boolean isPalindrome(String string) {
    int left = 0;
    int right = string.length() - 1;
    while (left < right) {
      if (string.charAt(left) != string.charAt(right)) {
        return false;
      }

      left++;
      right--;
    }

    return true;
  }

  // Returns the reversed string of the given string.
  private String reverseWord(String str) {
    // Leverage the existing library "StringBuilder" to reverse a string.
    return  new StringBuilder(str).reverse().toString();
  }

  private Set<String> findPalindromesHelper(
          String word, Set<String> reversedWords) {
    Set<String> palindromes = new HashSet<>();


    // Check if we can form a palindrome by concatenating two words with the
    // same length.
    if (reversedWords.contains(word)) {
      // Prevent forming a palindrome with a single word.
      String reversedWord = reverseWord(word);
      if (!reversedWord.equals(word)) {
        palindromes.add(word + reversedWord);
      }
    }

    // Check if we can form a palindrome by concatenating two words with
    // different length by appending the other word to the back of the
    // given word.
    for (int i = 1; i < word.length() - 1; i++) {
      String takenOutStr = word.substring(word.length() - i);
      String remainingStr = word.substring(0, word.length() - i);
      if (isPalindrome(takenOutStr) && reversedWords.contains(remainingStr)) {
        String palindrome =
                remainingStr + takenOutStr + reverseWord(remainingStr);
        palindromes.add(palindrome);
      }
    }

    // Check if we can form a palindrome by concatenating two words with
    // different length by appending the other word to the front of the
    // given word.
    for (int i = 1; i < word.length() - 1; i++) {
      String takenOutStr = word.substring(0, i);
      String remainingStr = word.substring(i);
      if (isPalindrome(takenOutStr) && reversedWords.contains(remainingStr)) {
        String palindrome =
                reverseWord(remainingStr) + takenOutStr + remainingStr;
        palindromes.add(palindrome);
      }
    }

    return palindromes;
  }

  Set<String> findPalindromes(List<String> words) {
    // Reverse each word and put it in a set.
    Set<String> reversedWords = new HashSet<>();
    for (String word : words) {
      reversedWords.add(reverseWord(word));
    }

    // Iterate through each word and check if we can pair up with another
    // word to form a palindrome.
    Set<String> palindromes = new HashSet<>();
    for (String word : words) {
      Set<String> palindromePairs =
              findPalindromesHelper(word, reversedWords);
      palindromes.addAll(palindromePairs);
    }

    return palindromes;
  }