在Python中找到子序列的长度,使它仍然是s的子序列

在Python中找到子序列的长度,使它仍然是s的子序列

假设我们有一个字符串s和另一个字符串t。t是s的子序列。我们必须找到我们可以从s中删除的最大子字符串长度,使得t仍然是s的子序列。

因此,如果输入如下s=”xyzxyxz” t=”yz”,则输出将是4,因为我们可以删除子字符串“abca”。

为了解决这个问题,我们将遵循以下步骤-

  • left:=一个新的列表, right:=也是一个新的列表

  • c1:=-1, c2:=-1,c3:=-1

  • j:=0

  • 对于i从0到s的长度,执行以下操作

    • 如果s[i]与t[j]相同,那么
      • 在左边的末尾插入i

      • j:=j+ 1

    • 如果j与t的长度相同,则

      • c1:=s的长度-i-1

      • 退出循环

  • j:=t的长度-1

  • 对于i从s的长度减一到0,递减1,执行以下操作

    • 如果s[i]与t[j]相同,则
      • 在右边的位置0插入i

      • j:=j-1

    • 如果j与-1相同,则

      • c2:=i

      • 退出循环

  • 对于i从0到t的长度-1,执行以下操作

    • c3:=max(c3,(right[i+1]-left[i]-1))
  • 返回c1、c2和c3的最大值

Python示例

让我们看下面的实现,以更好地理解-

class Solution:
   def solve(self, s, t):
      left = []
      right = []
      c1 = -1
      c2 = -1
      c3 = -1
      j = 0
      for i in range(len(s)):
         if s[i] == t[j]:
            left.append(i)
            j += 1
         if j == len(t):
            c1 = len(s) - i - 1
            break
      j = len(t) - 1
      for i in range(len(s) - 1, -1, -1):
         if s[i] == t[j]:
            right.insert(0, i)
            j -= 1
         if j == -1:
            c2 = i
            break
      for i in range(len(t) - 1):
         c3 =max(c3, right[i + 1] - left[i] - 1)
      return max(c1, c2, c3)
ob = Solution()
s = "xyzxyxz"
t = "yz"
print(ob.solve(s, t))

输入

"xyzxyxz", "yz"

输出

4

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程