Kiểm tra xem có thể chuyển đổi một chuỗi này sang chuỗi khác trong Python hay không

Giả sử chúng ta có hai chuỗi s và t, t viết hoa. Chúng ta phải kiểm tra xem chúng ta có thể chuyển đổi s thành t hay không bằng cách thực hiện các thao tác sau.

• Chuyển đổi một số chữ thường thành chữ hoa.
• Xóa tất cả các chữ cái thường.

Vì vậy, nếu đầu vào là s =​​"fanToM", t ="TOM", thì đầu ra sẽ là True vì chúng ta có thể thay đổi 'o' thành 'O' sau đó loại bỏ tất cả các chữ cái thường khác từ s để biến nó thành t.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s, m:=kích thước của t
• dp:=ma trận kích thước (m + 1) x (n + 1) và điền sai
• dp [0, 0]:=True
• đối với tôi trong phạm vi từ 0 đến kích thước là s-1, hãy thực hiện
  • đối với j trong phạm vi từ 0 đến kích thước của t, thực hiện
    • nếu dp [i, j] là True, thì
      • nếu j
      • dp [i + 1, j + 1]:=True
    • nếu s [i] không phải là chữ hoa thì
      • dp [i + 1, j]:=True

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(s,t):
   n = len(s)
   m = len(t)
   dp= [[False for i in range(m+1)] for i in range(n+1)]
   dp[0][0] = True
   for i in range(len(s)):
      for j in range(len(t)+1):
         if dp[i][j] == True:
            if j < len(t) and (s[i].upper() == t[j]):
               dp[i + 1][j + 1] = True
            if s[i].isupper()==False:
               dp[i + 1][j] = True
   return dp[n][m]
s = "fanToM"
t = "TOM"
print(solve(s, t))

Đầu vào

"fanToM", "TOM"

Đầu ra

True