如何编写高效算法判断无序单词集合能否组成回文句？

LeetCode上关于寻找回文对、判断单个字符串是否为回文的问题数不胜数，但我未找到针对无序单词集合的回文句验证相关讨论——函数返回true的前提是所有单词都必须被使用，拼接后的完整句子为回文。

示例 #

• 输入：

  ["stop", "nine", "rum", "myriad", "put", "up", "rum", "dairymen", "murmur", "in", "pots"]
  

  函数返回True；
• 输入：

  ["sit", "on", "potato", "pan", "otis"]
  

  函数返回False。

朴素解法的局限 #

Python中的朴素解法是使用itertools.permutations(words, len(words))遍历所有可能排列，但随着单词数量增加，时间复杂度至少为O(n!*c)（n为单词数，c为总字符数），完全不具备实用性。

现有排列算法的适配困境 #

• Heap's算法：并不适配该问题，因为当首尾单词无法构成回文结构的一部分时，难以通过生成半数排列来短路所有同外层配置的子排列，无法有效剪枝。
• Steinhaus–Johnson–Trotter算法：在排列生成过程中会出现反向重复的清晰分界，但我尚未想到高效短路无需检查场景的方法，或许可通过排除特定情况来跳过部分逆序数？

补充测试用例 #

极端挑战案例 #

以下示例的排列数约为10^157种，暴力解法完全无法处理：

['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111', '10000', '10001', '10010', '10011', '10100', '10101', '10110', '10111', '11000', '11001', '11010', '11011', '11100', '11101', '11110', '11111', '100000', '100001', '100010', '100011', '100100', '100101', '100110', '100111', '101000', '101001', '101010', '101011', '101100', '101101', '101110', '101111', '110000', '110001', '110010', '110011', '110100', '110101', '110110', '110111', '111000', '111001', '111010', '111011', '111100', '111101', '111110', '111111', '1000000', '1000001', '1000010', '1000011', '1000100', '1000101', '1000110', '1000111', '1001000', '1001001', '1001010', '1001011', '1001100', '1001101', '1001110', '1001111', '1010000', '1010001', '1010010', '1010011', '1010100', '1010101', '1010110', '1010111', '1011000', '1011001', '1011010', '1011011', '1011100', '1011101', '1011110', '1011111', '1100000', '1100001', '1100010', '1100011', '1100100']

常规测试用例 #

1. 返回False的输入：

   ['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111', '10000', '10001', '10010', '10011', '10100', '10101', '10110', '10111']
   

2. 返回True的输入：

   ['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111', '10000', '10001', '10010', '10011', '10100', '10101', '10110']
   

   对应的有效回文排列：

   ["1000", "1100", "110", "10100", "10011", "11", "1010", "1101", "1011", "1110", "10000", "10", "1111", "10110", "1", "10101", "111", "100", "10010", "101", "1001", "10001"]
   

内容的提问来源于stack exchange，提问作者brubsby