โปรแกรมนับจำนวนการต่อคำมีอยู่ในรายการใน python

สมมติว่าเรามีรายการสตริง เราต้องหาจำนวนคำที่ต่อกันจากคำอื่นๆ ในรายการด้วย เราสามารถนำคำกลับมาใช้ใหม่ได้เมื่อเชื่อมและต่อกันหลายครั้ง

ดังนั้น หากอินพุตเป็นเหมือนคำ =["hello", "world", "helloworld", "famous", "worldfamous", "programming"] ผลลัพธ์จะเป็น 2 เนื่องจาก "helloworld" ต่อจาก " สวัสดี" และ "โลก" "worldfamous" เป็นการผสมผสานระหว่าง "world" และ "famous"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• ลอง :=แผนที่ใหม่
• สำหรับแต่ละคำในคำ ทำ
  • เลเยอร์ :=พยายาม
  • สำหรับแต่ละคำ ให้ทำ
    • ถ้า w ไม่อยู่ในเลเยอร์ แล้ว
      • เลเยอร์[w] :=แผนที่ใหม่
    • เลเยอร์ :=ชั้น[w]
  • layer["*"] :=ทูเพิลว่าง
  • กำหนดฟังก์ชัน dfs() ต้องใช้ word, num_concatenated_words
  • เลเยอร์ :=พยายาม
  • สำหรับแต่ละดัชนี i และคำ w ในคำ ให้ทำ
    • ถ้า "*" อยู่ในเลเยอร์แล้ว
      • ถ้า dfs(word[จากดัชนี i ถึง end], num_concatenated_words + 1) เป็นจริง ดังนั้น
        • คืนค่า True
      • ถ้า w ไม่อยู่ในเลเยอร์ แล้ว
        • คืนค่าเท็จ
    • เลเยอร์ :=ชั้น[w]
  • ถ้า "*" อยู่ในเลเยอร์และ num_concatenated_words>=1 แล้ว
    • คืนค่า True
  • คืนค่าเท็จ
  • จากวิธีหลัก ให้ทำดังนี้:
  • นับ :=0
  • สำหรับแต่ละคำในคำ ทำ
    • นับ :=นับ + dfs(word, 0)
• จำนวนคืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

ตัวอย่าง

class Solution:
   def solve(self, words):
      trie = {}
      for word in words:
         layer = trie
         for w in word:
            if w not in layer:
               layer[w] = {}
            layer = layer[w]
         layer["*"] = ()

      def dfs(word, num_concatenated_words):
         layer = trie

         for i, w in enumerate(word):
            if "*" in layer:
               if dfs(word[i:], num_concatenated_words + 1):
                  return True
            if w not in layer:
               return False
            layer = layer[w]

         if "*" in layer and num_concatenated_words >= 1:
            return True
         return False

      count = 0
     for word in words:
      count += dfs(word, 0)
   return count

ob = Solution()
words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"]
print(ob.solve(words))

อินพุต

["hello", "world", "helloworld", "famous", "worldfamous", "programming"]

ผลลัพธ์

2