30/09/2018, 23:37
Looking for Python Experts ( Hóng cao nhân, cao kiến )
Mọi người chỉ giáo e câu này với
Your task is to make a palindrome string by rearranging and concatenating given words.
Ex : otwracar n ydh w tohdyn
Output should be : n ydh otwracar w tohdyn
Chỉ cần ý tưởng thôi là ok rồi
Bài liên quan
em chỉ nhận biết được một chỗ là cái này[quote=“masterq1997, post:1, topic:34045”]
n ydh otw
[/quote]
là ngược lại của chỗ này
Chuỗi palindrome là chuỗi đọc xuôi hay ngược đều giống nhau (đối xứng). Ví dụ:
Trong chuỗi palindrome, chỉ có nhiều nhất 1 kí tự xuất hiện 2n + 1 lần (số lẻ). Theo output của bạn, hình như khoảng trắng được đặt tùy ý. Ý tưởng bài này là tìm kì tự đứng giữa trước, rồi chia đều phần còn lại cho 2 bên là xong.
Không hiểu đề . Tóm lại là nhiệm vụ phải làm gì?
Cho một chuỗi như thế này : otwracar n ydh w tohdyn
xong bác phải sắp xếp lại các chữ để ra được palindrome
xắp xếp các chữ bác ơi, cách nhau bởi dấu cách chứ dấu cách k được đặt tùy ý
Gợi ý bạn dùng
itertools
, cópermutations
dùng để tạo hoán vị.Trước tiên tạo list các từ có trong input, sau đó tạo các hoán vị của các từ này rồi check xem nó có phải là palindrome hay ko. Khi check palindrome ko quan tâm tới khoảng trắng
OKay tks anh để em tìm hiểu xem :smile
thế chỉ được thay đổi vị trí từ mà không được thay đổi vị trí các chữ cái à?
Thì ý mình là vậy đó, ví dụ input chuỗi: bbaac.
Chỉ có duy nhất 1 kí tự có số lần xuất hiện lẻ là ‘c’ ==> c nằm ở giữa. Lúc đó chỉ cần tiếp tục chia mấy kí tự còn lại cho 2 bên: abcba, bacab.
Bạn lưu ý cách liệt kê tất cả hoán vị, cách này khá tốn thời gian với chuỗi lớn. Vì thuật toán tạo hoán vị có độ phức tạp O(n!)
words là từ, characters là ký tự (chữ cái)
Như bác @Tobi nói chuẩn đó, nếu len(s) % 2 != 0 thì tìm kí tự xuất hiện lẻ lần, lấy đó làm trung tâm; còn nếu len(s) % 2 == 0 thì tìm cặp kí tự giống nhau cạnh nhau trước.
Nếu bụp phát tìm tất cả hoán vị ngay thì rất tốn kém, cái input của bác có 5 từ còn ít chứ chỉ cần chục từ thôi là ăn đủ rồi.
Một cách khác: kiểm tra xem chữ cái bắt đầu của từ này có là chữ cái cuối cùng của một từ khác không. Như trong ví dụ của bạn chỉ có “n” bắt đầu bằng ‘n’ và “tohdyn” kết thúc bằng ‘n’. Thế là sắp xếp được ngay 2 từ rồi.
Chưa chắc vì sẽ có trường hợp input như thế này
fm mekrgobq fqbogrke m gzzgm
Mình không bảo là trường hợp nào cũng may mắn như thế. Nhưng kiểm tra như vậy cũng giảm kha khá số trường hợp phải xét rồi.
Permutations của itertools không tốn kém đâu bạn , mà theo đề bài là words, nhắc lại là words nhé, nên tính số ký tự lặp lại chẵn hay lẻ là sai đề rồi
Bạn có vẻ vẫn chưa hiểu ý của @Tobi và mình.
itertools vẫn tốn như thường nhé. Bạn xem thử đoạn code trong phần permutation. Trong documentation họ nói là tương đương với code trên, nên mình hiểu là độ phức tạp vẫn sẽ là O(n!) (để ý 2 vòng lặp while & for)
https://docs.python.org/2/library/itertools.html#itertools.permutations
Đoạn cuối còn nói là:
Vậy trong trường hợp r = n, lúc đó số tổ hợp sẽ là:
Độ phức tạp vẫn là O(n!)
Mình thì thấy tốn thời gian bàn luận về mấy cái độ phức tạp này nọ hơn là ngồi code, vì lúc nãy mình dùng mobile nên ko tiện, giờ mình gửi các bạn đoạn code xử lý đề bài trên:
Còn việc tốn thì các bạn đo bằng gì để biết nó tốn?
thử với chuỗi “a b c d c d e f e a b c c c c” xem nó chạy bao lâu
hoán vị của 5 phần tử là 5! ~ 120 hoán vị nên nó lẹ. Còn chuỗi trên có 15 từ thì 15! = 1300 tỷ hoán vị. Ngồi 1 tiếng chắc ra đó
Theo bạn thì mất bao lâu?
ồ vậy là nó break sớm. Vậy thêm 1 chữ z vô nữa đi Gút bai chờ sáng mai ra nha
mình ko có ý nói đây là cách sai, đây là cách đúng. Nhưng nói nó là cách lẹ thì ko đúng. Nếu số từ khoảng 10 từ thì ok, 100 từ thì cách duyệt trâu này ko nổi