336.Palindrome-Pairs

336. Palindrome Pairs

题目地址

https://leetcode.com/problems/palindrome-pairs/

题目描述

Given a list of unique words, find all pairs of distinct 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:
Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]] 
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:
Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]

代码

Approach #1 Brute force

Time Complexity : O(n^2*k) // and k be the length of the longest word.

class Solution {
  public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> pairs = new ArrayList();
    for (int i = 0; i < words.length; i++) {
      for (int j = 0; j < words.length; j++) {
        if (i == j)     continue;
        String combined = words[i].concat(words[j]);
        String reversed = new StringBuilder(combined).reverse().toString();
        if (combined.equals(reversed)) {
          pairs.add(Arrays.asList(i, j));
        }
      }
    }

    return pairs;
  }
}

Approach #2 Hashing

Time: O(k^2 * n) Space: O((k+n)^2)

Three Cases:

1. Check if the reverse of word is present. If it is, then we have a case 1 pair by appending the reverse onto the end of word.

2. For each suffix of word, check if the suffix is a palindrome. if it is a palindrome, then reverse the remaining prefix and check if it's in the list. If it is, then this is an example of case 2.

3. For each prefix of word, check if the prefix is a palindrome. if it is a palindrome, then reverse the remaining suffix and check if it's in the list. If it is, then this is an example of case 3.

class Solution {
  public List<List<Integer>> palindromePairs(String[] words) {
    Map<String, Integer> wordSet = new HashMap<>();
    for (int i = 0; i < words.length; i++) {
      wordSet.put(words[i], i);
    }

    List<List<Integer>> solution = new ArrayList();
    for (String word: wordSet.keySet()) {
      int currentWordIndex = wordSet.get(word);
      String reversedWord = new StringBuilder(word).reverse().toString();
      // case #1
      if (wordSet.containsKey(reversedWord) 
          && wordSet.get(reversed) != currentWordIndex) {

        solution.add(Arrays.asList(currentWordIndex, wordSet.get(reversedWord)));
      } 
      // case #2
      for (String suffix: allValidSuffixes(word)) {
        String reversedSuffix = new StringBuilder(suffix).reverse().toString();
        if (wordSet.containsKey(reversedSuffix)) {
          solution.add(Arrays.asList(wordSet.get(reversedSuffix), currentWordIndex));
        }
      }

      // case #3
      for (String prefix: allValidPrefixed(word)) {
        String reversedPrefix = new StringBuilder(prefix).reverse().toString();
        if (wordSet.containsKey(reversedPrefix)) {
          solution.add(Arrays.asList(currentWordIndex, wordSet.get(reversedPrefix)));
        }
      }
    }

    return solution;
  }

   private List<String> allValidPrefixes(String word) {
        List<String> validPrefixes = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            if (isPalindromeBetween(word, i, word.length() - 1)) {
                validPrefixes.add(word.substring(0, i));
            }
        }
        return validPrefixes;
    }

    private List<String> allValidSuffixes(String word) {
        List<String> validSuffixes = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            if (isPalindromeBetween(word, 0, i)) {
                validSuffixes.add(word.substring(i + 1, word.length()));
            }
        }
        return validSuffixes;
    }

     // Is the prefix ending at i a palindrome?
    private boolean isPalindromeBetween(String word, int front, int back) {
        while (front < back) {
            if (word.charAt(front) != word.charAt(back)) return false;
            front++;
            back--;
        }
        return true;
    }

}

Approach #3 Using a Trie

class TrieNode {
  public int wordEnding = -1;
  public Map<Character, TrieNode> next = new HashMap();
  public List<Integer> palindromePrefixRemaining = new ArrayList();
}

class Solution {
  public List<List<Integer>> palindromePairs(String[] words) {
    TrieNode trie = new TrieNode();

    // 1. build the Trie with reversed words
    for (int wordId = 0; wordId < words.length; wordId++) {
      String word = words[wordId];
      String reversedWord = new StringBuilder(word).reverse().toString();
      TrieNode currentTrieLevel = trie;
      for (int j = 0; j < reversedWord.length(); j++) {
        if (hasPalindromeRemaining(reversedWord, j)) {
          currentTrieLevel.palindromePrefixRemaining.add(wordId);
        }
        Character c = reversedWord.charAt(j);
        if (!currentTrieLevel.next.containsKey(c)) {
          currentTrieLevel.next.put(c, new TrieNode());
        }
        currentTrieLevel = currentTrieLevel.next.get(c);
      }
      currentTrieLevel.wordEnding = wordId;
    }

    // 2. Find Pairs
    List<List<Integer>> pairs = new ArrayList<>();
    for (int wordId = 0; wordId < words.length; wordId++) {
      String word = words[wordId];
      TrieNode currentTrieLevel = trie;
      for (int j = 0; j < word.length(); j++) {
        // case #3:  word:(xxx + Palindrome), trie: xxx
        if (currentTrieLevel.wordEnding != -1
           && hasPalindromeRemaining(word, j)) {
          pairs.add(Arrays.asList(wordId, currentTrieLevel.wordEnding));
        }

        Character c = word.charAt(j);
        currentTrieLevel = currentTrieLevel.next.get(c);
        if (currentTrieLevel == null)        break;
      }

      if (currentTrieLevel == null) continue;

      // case #1
      if (currentTrieLevel.wordEnding != -1 
          && currentTrieLevel.wordEnding != wordId) {
        pairs.add(Arrays.asList(wordId, currentTrieLevel.wordEnding));
      }

      // case #2: Trie:(Palindrome + xxx) , word:xxx
      for (int other: currentTrieLevel.palindromePrefixRemaining) {
        pairs.add(Arrays.asList(wordId, other));
      }
    }

    return pairs;
  }

  private boolean hasPalindromeRemaining(String s, int i) {
    int p1 = i;
    int p2 = s.length() - 1;
    while (p1 < p2) {
      if (s.charAt(p1) != s.charAt(p2))        return false;
      p1++;
      p2--;
    }
    return true;
  }
}