資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：生成所有可能的字串
假設我們有一個字串s，其中包含小寫字母字元以及其他字元，例如“[”、“|”和“]”。“[a|b|c]”表示可以選擇“a”、“b”或“c”作為可能性。我們必須找到一個包含s可以表示的所有可能值的字串列表。“[]”不能巢狀，可以有任意數量的選擇。
例如，如果輸入為s = "[d|t|l]im[e|s]"，則輸出將為['dime', 'dims', 'lime', 'lims', 'time', 'tims']
為了解決這個問題，我們將遵循以下步驟：
- 如果s為空，則
- 返回一個包含空字串的列表
- n := s的長度
- seq := 新列表，res := 新列表
- 定義一個函式helper()。它將接收pos作為引數
- 如果pos等於n，則
- 連線seq中存在的每個元素並將其插入res
- 否則，
- 如果s[從索引pos到結尾的子串]中包含“[”，則
- start := pos + s[從索引pos到結尾的子串]中“[”的索引
- end := pos + s[從索引pos到結尾的子串]中“]”的索引
- 對於s從start到end的子串（以“|”分割）中的每個選項，執行以下操作：
- 將s[從索引pos到start-1]插入seq的末尾
- 將選項插入seq的末尾
- helper(end + 1)
- 從seq中刪除最後兩個元素
- 如果s[從索引pos到結尾的子串]中包含“[”，則
- 否則，
- 將s[從索引pos到end]插入seq的末尾
- helper(n)
- 從seq中刪除最後一個元素
- 如果pos等於n，則
- 在主方法中執行以下操作：
- helper(0)
- 按排序順序返回res
讓我們來看下面的實現以更好地理解
示例
class Solution:
def solve(self, s):
if not s:
return [""]
n = len(s)
def helper(pos):
if pos == n:
res.append("".join(seq))
else:
if "[" in s[pos:]:
start = pos + s[pos:].index("[")
end = pos + s[pos:].index("]")
for option in s[start + 1 : end].split("|"):
seq.append(s[pos:start])
seq.append(option)
helper(end + 1)
seq.pop()
seq.pop()
else:
seq.append(s[pos:])
helper(n)
seq.pop()
seq = []
res = []
helper(0)
return sorted(res)
ob = Solution()
s = "[d|t|l]im[e|s]"
print(ob.solve(s))輸入
"[d|t|l]im[e|s]"
輸出
['dime', 'dims', 'lime', 'lims', 'time', 'tims']
更新於: 2020年11月26日
瀏覽量：353
廣告