336. Palindrome Pairs (Leetcode - Hard)

PalindromePairs.Java

class Solution {

  public String reverseString(String input) {
    return new StringBuffer(input).reverse().toString();
  }

  public boolean isPalindrome(String str) {
    if (str.length() == 0) return false;
    if (str.length() == 1) return true;
    char[] chars = str.toCharArray();
    int i = 0;
    int j = str.length() - 1;
    while (i < j) {
      if (chars[i] != chars[j])
        return false;
      i++;
      j--;
    }
    return true;
  }

  // optimization: loop them all o(n)
  public List<List<Integer>> palindromePairs(String[] words) {
    List<List<Integer>> ret = new LinkedList<>();
    Map<String, Integer> dict = new HashMap<>();
    // ::: very important part
    Set<Integer> setAvailLengths = new TreeSet<>(); // @todo try HashSet
    for (int i = 0; i < words.length; i++) {
      dict.put(reverseString(words[i]), i);
      // ::: very important part
      setAvailLengths.add(words[i].length());
    }
    // ret.addAll(handleEmptyString(dict, words));
    int emptyStringIdx = -1;
    if (dict.containsKey("")) {
      emptyStringIdx = dict.get("");
      for (int i = 0; i < words.length; i++) {
        if (emptyStringIdx != -1 && i != emptyStringIdx && isPalindrome(words[i])) {
          ret.add(List.of(i, emptyStringIdx));
          ret.add(List.of(emptyStringIdx, i));
        }
      }
    }
    //
    // ret.addAll(handleReverseString(dict, words));
    for (int i = 0; i < words.length; i++) {
      if (i == emptyStringIdx) continue;
      ////
      if (dict.containsKey(words[i]) && i != dict.get(words[i])) {// s is reverse of itself
        ret.add(List.of(i, dict.get(words[i])));
      }
      ////
      // ret.addAll(handleSubString(dict, words));
      for (int k : setAvailLengths) {
        // ::: avoid lengths greater than word in question
        if (k == words[i].length()) break;
        // avoid recalculating the empty string
        if (k == 0) continue;
        //System.out.println(words[i] + " " + words[i].length() + " " + k);
        int j = words[i].length() - k;
        String prefix = words[i].substring(0, j);
        String suffix = words[i].substring(j);
        var idx = extracted(dict, i, prefix, suffix);
        if (idx != null) ret.add(Arrays.asList(idx, i));
        j = k;
        prefix = words[i].substring(0, j);
        suffix = words[i].substring(j);
        idx = extracted(dict, i, suffix, prefix);
        if (idx != null) ret.add(Arrays.asList(i, idx));
      }
    }
    return ret;
  }

  private Integer extracted(Map<String, Integer> dict, int currWordIdx, String palindrome, String remainder) {
    if (!palindrome.isEmpty() && !palindrome.isEmpty()) {
      if (isPalindrome(palindrome)) {
        if (dict.containsKey(remainder)) {
          int idx = dict.get(remainder);
          if (idx != currWordIdx && idx != -1)
            return idx;
        }
      }
    }
    return null;
  }
}