Giả sử chúng ta có hai chuỗi s và t chỉ có ba ký tự 'A', 'B' và '#'. Chúng ta phải kiểm tra xem có thể chuyển s thành t hay không bằng cách thực hiện các thao tác này trên s.
- 'A' chỉ có thể di chuyển sang phía bên trái
- 'B' chỉ có thể di chuyển sang phía bên tay phải
- Cả 'A' và 'B' đều không thể vượt nhau
Vì vậy, nếu đầu vào giống như s ="## AB ## B" t ="A ### B # B", thì đầu ra sẽ là True vì trong s A có thể dễ dàng di chuyển sang vị trí bên trái nhất và giữa B có thể di chuyển một bước sang phải
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- s:=một danh sách bằng cách lấy các ký tự từ s
- t:=một danh sách bằng cách lấy các ký tự từ t
- nếu kích thước của s không giống với kích thước của t, thì
- trả về Sai
- nếu số lượng 'A' trong s và t khác nhau hoặc số lượng 'B' trong s và t khác nhau hoặc, thì
- trả về Sai
- đố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
- nếu s [i] không giống với '#', thì
- đối với j trong phạm vi từ 0 đến kích thước của t - 1, thực hiện
- nếu (t [j] không giống với s [i]) và t [j] không giống với '#', thì
- trả về Sai
- nếu t [j] giống với s [i], thì
- t [j]:='#'
- nếu s [i] giống với 'A' và i
- trả về Sai
- nếu s [i] giống với 'B' và i> j, thì
- trả về Sai
- ra khỏi vòng lặp
- nếu (t [j] không giống với s [i]) và t [j] không giống với '#', thì
- đối với j trong phạm vi từ 0 đến kích thước của t - 1, thực hiện
- nếu s [i] không giống với '#', thì
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):
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)) Đầu vào
"##AB##B", "A###B#B"
Đầu ra
True