資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：檢查字串是否可以透過子串排序操作進行轉換
假設我們有兩個數字字串s和t，我們希望使用以下操作任意多次將字串s轉換為t：1. 選擇s中的一個非空子串，並對其進行就地排序，使字元按升序排列。我們必須檢查是否可以將字串s轉換為t。
因此，如果輸入類似於s = "95643" t = "45963"，則輸出為True，因為我們可以透過例如"95643" -> "95463" -> "45963" 將s轉換為t。
為了解決這個問題，我們將遵循以下步驟：
places := 一個對映，其預設值型別為列表
對於範圍從s的大小到0的i，執行：
key := 將s[i]作為整數
在places[key]的末尾插入i
對於t中的每個e，執行：
key := 將e作為整數
如果places[key]為空，則
返回False
i := places[key]的最後一個元素
對於範圍從0到key - 1的j，執行：
如果places[j]非空且places[j]的最後一個元素 < i，則
返回False
從places[key]中刪除最後一個元素
返回True
示例
讓我們看下面的實現以更好地理解
from collections import defaultdict
def solve(s, t):
places = defaultdict(list)
for i in reversed(range(len(s))):
key = int(s[i])
places[key].append(i)
for e in t:
key = int(e)
if not places[key]:
return False
i = places[key][-1]
for j in range(key):
if places[j] and places[j][-1] < i:
return False
places[key].pop()
return True
s = "95643"
t = "45963"
print(solve(s, t))輸入
"95643", "45963"
輸出
True
更新於：2021年10月6日
91 次瀏覽
廣告