Welcome to Subscribe On Youtube

336. Palindrome Pairs

Description

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

• 0 <= i, j < words.length,
• i != j, and
• words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.

You must write an algorithm with O(sum of words[i].length) runtime complexity.

 

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

Example 2:

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

Example 3:

Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["a","a"]

 

Constraints:

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lowercase English letters.

Solutions

• Java
• Python
• Go
• C#

• class Solution {
      private static final int BASE = 131;
      private static final long[] MUL = new long[310];
      private static final int MOD = (int) 1e9 + 7;
      static {
          MUL[0] = 1;
          for (int i = 1; i < MUL.length; ++i) {
              MUL[i] = (MUL[i - 1] * BASE) % MOD;
          }
      }
      public List<List<Integer>> palindromePairs(String[] words) {
          int n = words.length;
          long[] prefix = new long[n];
          long[] suffix = new long[n];
          for (int i = 0; i < n; ++i) {
              String word = words[i];
              int m = word.length();
              for (int j = 0; j < m; ++j) {
                  int t = word.charAt(j) - 'a' + 1;
                  int s = word.charAt(m - j - 1) - 'a' + 1;
                  prefix[i] = (prefix[i] * BASE) % MOD + t;
                  suffix[i] = (suffix[i] * BASE) % MOD + s;
              }
          }
          List<List<Integer>> ans = new ArrayList<>();
          for (int i = 0; i < n; ++i) {
              for (int j = i + 1; j < n; ++j) {
                  if (check(i, j, words[j].length(), words[i].length(), prefix, suffix)) {
                      ans.add(Arrays.asList(i, j));
                  }
                  if (check(j, i, words[i].length(), words[j].length(), prefix, suffix)) {
                      ans.add(Arrays.asList(j, i));
                  }
              }
          }
          return ans;
      }
  
      private boolean check(int i, int j, int n, int m, long[] prefix, long[] suffix) {
          long t = ((prefix[i] * MUL[n]) % MOD + prefix[j]) % MOD;
          long s = ((suffix[j] * MUL[m]) % MOD + suffix[i]) % MOD;
          return t == s;
      }
  }
  

• class Solution:
      def palindromePairs(self, words: List[str]) -> List[List[int]]:
          d = {w: i for i, w in enumerate(words)}
          ans = []
          for i, w in enumerate(words):
              for j in range(len(w) + 1):
                  a, b = w[:j], w[j:]
                  ra, rb = a[::-1], b[::-1]
                  if ra in d and d[ra] != i and b == rb:
                      ans.append([i, d[ra]])
                  if j and rb in d and d[rb] != i and a == ra:
                      ans.append([d[rb], i])
          return ans
  
  

• func palindromePairs(words []string) [][]int {
  	base := 131
  	mod := int(1e9) + 7
  	mul := make([]int, 310)
  	mul[0] = 1
  	for i := 1; i < len(mul); i++ {
  		mul[i] = (mul[i-1] * base) % mod
  	}
  	n := len(words)
  	prefix := make([]int, n)
  	suffix := make([]int, n)
  	for i, word := range words {
  		m := len(word)
  		for j, c := range word {
  			t := int(c-'a') + 1
  			s := int(word[m-j-1]-'a') + 1
  			prefix[i] = (prefix[i]*base)%mod + t
  			suffix[i] = (suffix[i]*base)%mod + s
  		}
  	}
  	check := func(i, j, n, m int) bool {
  		t := ((prefix[i]*mul[n])%mod + prefix[j]) % mod
  		s := ((suffix[j]*mul[m])%mod + suffix[i]) % mod
  		return t == s
  	}
  	var ans [][]int
  	for i := 0; i < n; i++ {
  		for j := i + 1; j < n; j++ {
  			if check(i, j, len(words[j]), len(words[i])) {
  				ans = append(ans, []int{i, j})
  			}
  			if check(j, i, len(words[i]), len(words[j])) {
  				ans = append(ans, []int{j, i})
  			}
  		}
  	}
  	return ans
  }
  

• using System.Collections.Generic;
  using System.Linq;
  
  public class Solution {
      public IList<IList<int>> PalindromePairs(string[] words) {
          var results = new List<IList<int>>();
          var reverseDict = words.Select((w, i) => new {Word = w, Index = i}).ToDictionary(w => new string(w.Word.Reverse().ToArray()), w => w.Index);
  
          for (var i = 0; i < words.Length; ++i)
          {
              var word = words[i];
              for (var j = 0; j <= word.Length; ++j)
              {
                  if (j > 0 && IsPalindrome(word, 0, j - 1))
                  {
                      var suffix = word.Substring(j);
                      int pairIndex;
                      if (reverseDict.TryGetValue(suffix, out pairIndex) && i != pairIndex)
                      {
                          results.Add(new [] { pairIndex, i});
                      }
                  }
                  if (IsPalindrome(word, j, word.Length - 1))
                  {
                      var prefix = word.Substring(0, j);
                      int pairIndex;
                      if (reverseDict.TryGetValue(prefix, out pairIndex) && i != pairIndex)
                      {
                          results.Add(new [] { i, pairIndex});
                      }
                  }
              }
          }
  
          return results;
      }
  
      private bool IsPalindrome(string word, int startIndex, int endIndex)
      {
          var i = startIndex;
          var j = endIndex;
          while (i < j)
          {
              if (word[i] != word[j]) return false;
              ++i;
              --j;
          }
          return true;
      }
  }
  

All Problems

All Solutions