資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢K相似字串的最小K值
假設我們有兩個字串s和t。如果我們可以精確交換s中兩個字母的位置K次，使得結果字串為t，則這兩個字串是K相似的。因此，我們有兩個異位詞s和t，我們需要找到s和t為K相似的最小K值。
所以，如果輸入類似於s = "abc" t = "bac"，則輸出將為1。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式neighbors()。這將接收new_data作為輸入。
對於new_data中的每個索引i和值c，執行以下操作：
如果c與t[i]不同，則
退出迴圈。
對於從i+1到new_data大小-1的範圍內的每個j，執行以下操作：
如果u[j]與t[i]相同，則
交換new_data[i]和new_data[j]。
透過連線new_data中的所有元素生成一個字串並返回，從下一次呼叫開始，從該區域重新開始。
交換new_data[i]和new_data[j]。
從主方法中執行以下操作：
q := 建立一個佇列並插入(s, 0)對。
seen := 從s建立一個新的集合。
當q不為空時，執行以下操作：
(u, swap_cnt) := q的第一個元素，並將其從q中刪除。
如果u與t相同，則
返回swap_cnt。
對於neighbors(u作為列表)中的每個v，執行以下操作：
如果v不在seen中，則
標記v為已訪問。
將(v, swap_cnt+1)插入到q的末尾。
返回0。
示例
讓我們看看以下實現以更好地理解。
from collections import deque
def solve(s, t):
def swap(data, i, j):
data[i], data[j] = data[j], data[i]
def neighbors(new_data):
for i, c in enumerate(new_data):
if c != t[i]: break
for j in range(i+1, len(new_data)):
if u[j] == t[i]:
swap(new_data, i, j)
yield "".join(new_data)
swap(new_data, i, j)
q = deque([(s, 0)])
seen = set(s)
while q:
u, swap_cnt = q.popleft()
if u == t:
return swap_cnt
for v in neighbors(list(u)):
if v not in seen:
seen.add(v)
q.append((v, swap_cnt+1))
return 0
s = "abc"
t = "bac"
print(solve(s, t))輸入
"abc, bac"
輸出
1
更新於: 2021年10月8日
181 次瀏覽
廣告