Python程式：統計字元差異僅為一個的子字串

假設我們有兩個字串 s 和 t，我們需要找到從 s 中選擇一個非空子字串，並將其中的一個字元替換成另一個不同字元，使得替換後的子字串成為 t 的一個子字串的方法數。我們需要找到滿足上述條件的子字串數量。

例如，如果輸入為 s = "sts" t = "tsts"，則輸出為 6，因為以下是從 s 和 t 中選擇的子字串對，它們只有一個字元不同：

• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts")

加粗的部分是分別從兩個字串 s 和 t 中選擇的子字串。

為了解決這個問題，我們將遵循以下步驟：

• n1 := s 的長度
• n2 := t 的長度
• ans := 0
• 對於 s 中的每個索引 i1 和字元 c1：
  • 對於 t 中的每個索引 i2 和字元 c2：
    • i := i1，j := i2
    • 當 i < n1 且 j < n2 且 s[i] 等於 t[j] 時：
      • i := i + 1，j := j + 1
    • 如果 i < n1 且 j < n2 且 s[i] 不等於 t[j]，則
      • i := i + 1，j := j + 1
      • ans := ans + 1
      • 當 i < n1 且 j < n2 且 s[i] 等於 t[j] 時：
        • i := i + 1，j := j + 1
        • ans := ans + 1
• 返回 ans

示例

讓我們看看下面的實現以更好地理解：

def solve(s, t):
   n1 = len(s)
   n2 = len(t)
   ans = 0

   for i1, c1 in enumerate(s):
      for i2, c2 in enumerate(t):
         i = i1
         j = i2

         while i < n1 and j < n2 and s[i] == t[j]:
            i += 1
            j += 1

         if i < n1 and j < n2 and s[i] != t[j]:
            i += 1
            j += 1
            ans += 1
            while i < n1 and j < n2 and s[i] == t[j]:
               i += 1
               j += 1
               ans += 1

   return ans

s = "sts"
t = "tsts"
print(solve(s, t))

輸入

"sts", "tsts"

輸出

6

Arnab Chakraborty

更新於： 2021年10月5日

瀏覽量：189

開啟你的 職業生涯

透過完成課程獲得認證

立即開始