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

สมมติว่าเรามีสองสตริง s และ t โดยมีอักขระเพียงสามตัว 'A', 'B' และ '#' เราต้องตรวจสอบว่าเป็นไปได้หรือไม่ที่จะแปลง s เป็น t โดยดำเนินการกับ s เหล่านี้

'A' ขยับได้ทางซ้ายมือเท่านั้น
'B' ขยับได้เฉพาะด้านขวามือเท่านั้น
ทั้ง 'A' และ 'B' ไม่สามารถข้ามกันได้

ดังนั้น หากอินพุตเป็น s ="##AB##B" t ="A###B#B" ผลลัพธ์จะเป็น True เนื่องจากใน s A สามารถเลื่อนไปทางซ้ายสุดได้ง่าย และตรงกลาง B สามารถเลื่อนไปทางขวาได้หนึ่งก้าว

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

s :=รายการโดยนำอักขระจาก s
t :=รายการโดยนำอักขระจาก t
ถ้าขนาดของ s ไม่เหมือนกับขนาดของ t แล้ว
- คืนค่าเท็จ
ถ้าจำนวน 'A' ใน s และ t ต่างกัน หรือการนับ 'B' ใน s และ t ต่างกัน หรือ
- คืนค่าเท็จ
สำหรับฉันในช่วง 0 ถึงขนาด s - 1 ทำ
- ถ้า s[i] ไม่เหมือนกับ '#' แล้ว
  - สำหรับ j ในช่วง 0 ถึงขนาด t - 1 ให้ทำ
    - ถ้า (t[j] ไม่เหมือนกับ s[i]) และ t[j] ไม่เหมือนกับ '#' ดังนั้น
      - คืนค่าเท็จ
    - ถ้า t[j] เหมือนกับ s[i] แล้ว
      - t[j] :='#'
      - ถ้า s[i] เหมือนกับ 'A' และฉัน
      - คืนค่าเท็จ
    - ถ้า s[i] เหมือนกับ 'B' และ i> j แล้ว
      - คืนค่าเท็จ
    - ออกมาจากลูป

คืนค่า True

ตัวอย่าง

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

def solve(s, t):
   s = list(s)
   t = list(t)
   if len(s) != len(t):
      return False
   if s.count('A') != t.count('A') or s.count('B') != t.count('B'):
      return False
   for i in range(len(s)):
      if s[i] != '#':
         for j in range(len(t)):
            if (t[j] != s[i]) and t[j] != '#':
               return False
            if t[j] == s[i]:
               t[j] = '#'
               if s[i] == 'A' and i < j:
                  return False
               if s[i] == 'B' and i > j:
                  return False
               break
   return True
s = "##AB##B"
t = "A###B#B"
print (solve(s, t))

อินพุต

"##AB##B", "A###B#B"

ผลลัพธ์

True