ตรวจสอบว่าสามารถแปลงสตริงหนึ่งเป็นสตริงอื่นใน Python . ได้หรือไม่

สมมติว่าเรามีสองสตริง s และ t, t เป็นตัวพิมพ์ใหญ่ เราต้องตรวจสอบว่าเราสามารถแปลง s เป็น t ได้หรือไม่โดยดำเนินการดังต่อไปนี้

• แปลงอักษรตัวพิมพ์เล็กบางตัวพิมพ์ใหญ่
• ลบอักษรตัวพิมพ์เล็กทั้งหมด

ดังนั้น หากอินพุตเป็น s ="fanToM", t ="TOM" ผลลัพธ์จะเป็น True เนื่องจากเราสามารถเปลี่ยน 'o' เป็น 'O' ได้ จากนั้นจึงลบอักษรตัวพิมพ์เล็กอื่นๆ ทั้งหมดออกจาก s เพื่อให้เป็น t

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ s, m :=ขนาดของ t
• dp:=เมทริกซ์ขนาด (m + 1)x(n + 1) และเติมด้วย False
• dp[0, 0] :=จริง
• สำหรับฉันในช่วง 0 ถึงขนาด s - 1 ทำ
  • สำหรับ j ในช่วง 0 ถึงขนาดของ t ทำ
    • ถ้า dp[i, j] เป็น True แล้ว
      • ถ้า j <ขนาดของ t และ s[i] เป็นตัวพิมพ์ใหญ่เหมือนกับ t[j] แล้ว
        • dp[i + 1, j + 1] :=จริง
      • ถ้า s[i] ไม่เป็นตัวพิมพ์ใหญ่
        • dp[i + 1, j] :=จริง
• ส่งคืน dp[n, m]

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

"fanToM", "TOM"

ผลลัพธ์

True