Leetcode

LeetCode 336.パリンドロームペア（トライ）



Leetcode 336 Palindrome Pairs



ハード

一意の単語のリストを指定して、指定されたリストで個別のインデックス（i、j）のすべてのペアを見つけます。これにより、2つの単語の連結、つまり、words [i] + words [j]が回文になります。



例1：

入力：[“ abcd”、“ dcba”、“ lls”、“ s”、“ sssll”]
出力：[[0,1]、[1,0]、[3,2]、[2,4]]
説明：回文は[“ dcbaabcd”、“ abcddcba”、“ slls”、“ llssssll”]です。
例2：



入力：[「bat」、「tab」、「cat」]
出力：[[0,1]、[1,0]]
説明：回文は[“ battab”、“ tabbat”]です。

問題の意味

文字列配列が与えられた場合、配列内の2つの異なる文字列を見つけるために、スプライシングは回文文字列にすることができます

考え

文字列文字列sとtを4つのケースの回文文字列にスプライスしました：



  1. s回文の空の文字列は文字列です&& t || T &&回文文字列sは空の文字列=> s + t、t + sは回文文字列
  2. tはsの逆です=> s + t、t + sは回文文字列です
  3. sはs1、s2stに分けることができます。 s1 + s2 == s && s1 && s2パリンドロームストリングt => t + sパリンドロームストリングの逆順
  4. sはs1、s2stに分けることができます。 s1 + s2 == s && s1は逆&& s2t回文文字列=> s + tは回文文字列

文字列配列を格納して試行すると、文字列検索効率のO（w）を達成できます。合計時間計算量はO（nw）です。ここで、nは文字列配列の長さ、wは最長の文字列の長さです。

コード

class Solution { class TrieNode { public int index = -1 public TrieNode[] next = new TrieNode[26] public TrieNode(int _index) { index = _index } } private void addPair(List<List<Integer>> ans, int n1, int n2) { List<Integer> tmp = new ArrayList<Integer>() tmp.add(n1) tmp.add(n2) ans.add(tmp) } private boolean checkPalindrome(String s) { int i = 0, n = s.length() for (i=0 i<n/2 ++i) { if (s.charAt(i) != s.charAt(n-1-i)) { return false } } return true } private int searchTrie(String s, TrieNode root) { if (s.isEmpty()) { return root.index } for (char ch: s.toCharArray()) { if (root.next[ch - 'a'] != null) { root = root.next[ch - 'a'] } else { return -1 } } return root.index } public List<List<Integer>> palindromePairs(String[] words) { int i = 0 TrieNode root = new TrieNode(-1), ptr = root, node = root for (String word: words) { ptr = root if (word.isEmpty()) { root.index = i++ continue } int j = 0, w = word.length() for (j=0 j<w ++j) { if (ptr.next[word.charAt(j) - 'a'] == null) { node = new TrieNode(-1) ptr.next[word.charAt(j) - 'a'] = node } ptr = ptr.next[word.charAt(j) - 'a'] if (j == w-1) { ptr.index = i++ } } } i = 0 ArrayList<List<Integer>> ans = new ArrayList<>() for (String word: words) { if (checkPalindrome(word)) { int ind = searchTrie('', root) if (ind != -1 && ind != i) { addPair(ans, i, ind) addPair(ans, ind, i) } } else { int cr = searchTrie(new StringBuilder(word).reverse().toString(), root) if (cr != -1 && cr != i) { addPair(ans, i, cr) } } int w = word.length(), j = 1 for (j=1 j<w ++j) { int cr = searchTrie(new StringBuilder(word.substring(j, w)).reverse().toString(), root) if (checkPalindrome(word.substring(0, j)) && cr != -1 && cr != i) { addPair(ans, cr, i) } cr = searchTrie(new StringBuilder(word.substring(0, j)).reverse().toString(), root) if (checkPalindrome(word.substring(j, w)) && cr != -1 && cr != i) { addPair(ans, i, cr) } } ++i } return ans } }