資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：統計列表中單詞串聯的數量
假設我們有一個字串列表；我們需要找到列表中哪些單詞是由列表中其他單詞串聯而成的。在串聯時可以重複使用單詞，並且可以進行任意次數的串聯。
例如，如果輸入是words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"]，則輸出為2，因為"helloworld"是"hello"和"world"的串聯。"worldfamous"是"world"和"famous"的串聯。
為了解決這個問題，我們將遵循以下步驟：
- trie := 一個新的對映
- 對於words中的每個單詞，執行以下操作：
- layer := trie
- 對於單詞中的每個字元w，執行以下操作：
- 如果layer中不存在w，則：
- layer[w] := 一個新的對映
- layer := layer[w]
- 如果layer中不存在w，則：
- layer["*"] := 一個空元組
- 定義一個函式dfs()。它將接收單詞和已串聯單詞數作為引數。
- layer := trie
- 對於單詞中的每個索引i和字元w，執行以下操作：
- 如果layer中存在"*"，則：
- 如果dfs(word[從索引i到結尾], num_concatenated_words + 1)為True，則：
- 返回True
- 如果layer中不存在w，則：
- 返回False
- 如果dfs(word[從索引i到結尾], num_concatenated_words + 1)為True，則：
- layer := layer[w]
- 如果layer中存在"*"，則：
- 如果layer中存在"*"且已串聯單詞數>=1，則：
- 返回True
- 返回False
- 在主方法中，執行以下操作：
- count := 0
- 對於words中的每個單詞，執行以下操作：
- count := count + dfs(word, 0)
- 返回count
讓我們看下面的實現來更好地理解。
示例
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
更新於: 2020年11月26日
瀏覽量：131
廣告