Giả sử chúng ta có một chuỗi s. Chúng tôi phải xóa những ký tự đã xuất hiện trước đó và trả về chuỗi đã rút gọn. Để giải quyết vấn đề này, chúng tôi sẽ sử dụng một từ điển có thứ tự để duy trì thứ tự chèn của các ký tự. Giá trị sẽ là tần số của các ký tự đó, tuy nhiên giá trị tần số không quan trọng ở đây. Sau khi tạo từ điển, chúng ta có thể chỉ cần lấy các khóa và nối chúng để lấy chuỗi.
Vì vậy, nếu đầu vào là s ="cabbbaadac", thì đầu ra sẽ là "cabd".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- d:=một từ điển nơi các khóa được lưu trữ theo thứ tự chèn của chúng
- đối với mỗi ký tự c trong s, thực hiện
- nếu c không có trong d, thì
- d [c]:=0
- d [c]:=d [c] + 1
- nếu c không có trong d, thì
- nối các khóa lần lượt theo thứ tự thích hợp để tạo chuỗi đầu ra và trả về.
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
from collections import OrderedDict def solve(s): d = OrderedDict() for c in s: if c not in d: d[c] = 0 d[c] += 1 return ''.join(d.keys()) s = "cabbbaadac" print(solve(s))
Đầu vào
"cabbbaadac"
Đầu ra
cabd