資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢相等子字串對的數量
假設我們有兩個字串，都由小寫字母組成。我們需要找到滿足以下條件的四元組 (p, q, r, s) 的數量：
0 <= p <= q <= 第一個字串的長度。
0 <= r <= s <= 第二個字串的長度。
第一個字串從索引 p 開始到索引 q 結束的子字串必須等於第二個字串從索引 r 開始到索引 s 結束的子字串。
在所有滿足上述條件的四元組中，q - r 必須是最小值。
我們需要找到此類四元組的數量。
例如，如果輸入為 firstString = 'hgfn'，secondString = 'gfrt'，則輸出為 2。
有兩個四元組 (1, 1, 0, 0) 和 (2, 2, 1, 1) 滿足條件，並且 q - r 的值為最小值。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 ord()。它將接收字元 ch
- 返回 ch 的 Unicode 值
- 在主方法中執行以下操作：
- left := 一個大小為 26 的新列表，其值為無窮大
- right := 一個大小為 26 的新列表，其值為 -1
- res := 0
- mi := 無窮大
- 對於第一個字串中的每個索引 i 和字元 ch，執行：
- left[ord(ch) - ord('a') ] := min(left[ord(ch) - ord('a') ], i)
- 對於第二個字串中的每個索引 i 和字元 ch，執行：
- right[ord(ch) - ord('a') ] := max(right[ord(ch) - ord('a') ], i)
- 對於 i in range(0, 25)：
- 如果 left[i] 不等於 -1，則
- mi := min(mi, left[i] - right[i])
- 如果 left[i] 不等於 -1，則
- 對於 i in range(0, 25)：
- 如果 left[i] 不等於無窮大且 right[i] 不等於 -1，則
- 如果 left[i] - right[i] 等於 mi，則
- res := res + 1
- 如果 left[i] - right[i] 等於 mi，則
- 如果 left[i] 不等於無窮大且 right[i] 不等於 -1，則
- 返回 res
示例
讓我們看下面的實現，以便更好地理解：
def solve(firstString, secondString):
left = [float('inf')] * 26
right = [-1] * 26
res = 0
mi = float('inf')
for i, ch in enumerate(firstString):
left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
for i, ch in enumerate(secondString):
right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
for i in range(26):
if left[i] != -1:
mi = min(mi, left[i] - right[i])
for i in range(26):
if left[i] != float('inf') and right[i] != -1:
if left[i] - right[i] == mi:
res += 1
return res
print(solve('hgfn', 'gfrt'))輸入
'hgfn', 'gfrt'
輸出
2
更新於：2021年10月7日
298 次檢視
廣告