資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢最長異位詞子序列的長度
假設我們有兩個小寫字串 S 和 T，我們需要找到最長異位詞子序列的長度。
因此，如果輸入類似於 S = "helloworld"，T = "hellorld"，則輸出將為 8
為了解決這個問題，我們將遵循以下步驟：
c := 一個新的對映，d := 一個新的對映
對於範圍從 0 到 a 的大小，執行以下操作
如果 a[i] 在 c 中，則
c[a[i]] := c[a[i]] + 1
否則，
c[a[i]] := 1
對於範圍從 0 到 b 的大小，執行以下操作
如果 b[i] 在 d 中，則
d[b[i]] := d[b[i]] + 1
否則，
d[b[i]] := 1
res := 0
對於 c 中的每個字元 ch，執行以下操作
如果 d[ch] > 0，則
res := res + c[ch] 和 d[ch] 的最小值
返回 res
讓我們看看以下實現以獲得更好的理解：
示例
class Solution:
def solve(self, a, b):
c, d = {}, {}
for i in range(len(a)):
if a[i] in c:
c[a[i]] += 1
else:
c[a[i]] = 1
for i in range(len(b)):
if b[i] in d:
d[b[i]] += 1
else:
d[b[i]] = 1
res = 0
for ch in c:
if d.get(ch, 0) > 0:
res += min(c[ch], d[ch])
return res
ob = Solution()
S = "helloworld"
T = "hellorld"
print(ob.solve(S, T))輸入
S = "helloworld", T = "hellorld"
輸出
1
更新於: 2020年10月10日
270 次瀏覽
廣告