Python程序:查找将单词连接起来构成回文串的方法数


假设我们有一组不同的单词,我们需要找到将两个不同的单词从给定单词列表中连接起来构成回文串的不同方法数。

因此,如果输入类似于 words = ["time", "emit", "mo", "m"],则输出将为 3,因为我们可以构成 "timeemit"、"emittime" 和 "mom"。

为了解决这个问题,我们将遵循以下步骤:

  • res := 0

  • ln := 数组中的单词数量

  • 对于 k 从 0 到 1 的范围:

    • 对于 i 从 0 到 ln - 1 的范围:

      • 对于 j 从 i + 1 到 ln - 1 的范围:

        • res := res + (当 words[i] 与 words[j] 连接后是回文串时为 1,否则为 0)

    • words := 反转后的 words

  • 返回 res

让我们看看下面的实现,以便更好地理解:

示例

 在线演示

class Solution:
   def solve(self, words):
      def is_palindrome(w1, w2):
         w3 = w1 + w2
         return w3 == w3[::−1]
      res = 0
      ln = len(words)
      for k in range(2):
         for i in range(ln):
            for j in range(i + 1, ln):
               res += is_palindrome(words[i], words[j])
            words = words[::−1]
      return res
ob = Solution()
words = ["time", "emit", "mo", "m"]
print(ob.solve(words))

输入

["time", "emit", "mo", "m"]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

3

更新于:2020年12月15日

124 次浏览

启动您的职业生涯

完成课程获得认证

开始
广告