Make a palindrome string by rearranging and concatenating given words

#1

Mọi người chỉ giáo e câu này với :joy:

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 :joy:

#2

:smile: em chỉ nhận biết được một chỗ là cái này

là ngược lại của chỗ này

#3

Chuỗi palindrome là chuỗi đọc xuôi hay ngược đều giống nhau (đối xứng). Ví dụ:

  • abcba --> c xuất hiện 1 lần
  • aaabbaaa --> ko có kí tự nào
  • Amor Roma -->

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.

1 Like
#4

Không hiểu đề :rolling_eyes:. Tóm lại là nhiệm vụ phải làm gì?

#5

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

#6

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 ý

#7

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

1 Like
#8

OKay tks anh để em tìm hiểu xem :smile:

#9

thế chỉ được thay đổi vị trí từ mà không được thay đổi vị trí các chữ cái à?

#10

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

#11

words là từ, characters là ký tự (chữ cái)

#12

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.

2 Likes
#13

Chưa chắc vì sẽ có trường hợp input như thế này fm mekrgobq fqbogrke m gzzgm

#14

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.

#15

Permutations của itertools không tốn kém đâu bạn :smile:, 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

#16

Bạn có vẻ vẫn chưa hiểu ý của @Tobi và mình.

#17

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à:

The number of items returned is n! / (n-r)! when 0 <= r <= n
or zero when r > n.

Vậy trong trường hợp r = n, lúc đó số tổ hợp sẽ là:

\frac{n!}{(n-n)!} = n!

Độ phức tạp vẫn là O(n!)

#18

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:

from itertools import permutations

def is_palindrome(words):
    s = ''.join(words)
    return s == s[::-1]

def make_palindrome(s):
    for case in permutations(s.split()):
        if is_palindrome(case):
            return ' '.join(case)
    return 'Can not make palindrome string from given words'

%%time
make_palindrome('otwracar n ydh w tohdyn')
# CPU times: user 0 ns, sys: 0 ns, total: 0 ns
# Wall time: 55.3 µs

'n ydh otwracar w tohdyn'

%%time
make_palindrome('fm mekrgobq fqbogrke m gzzgm')
# CPU times: user 0 ns, sys: 0 ns, total: 0 ns
# Wall time: 31.9 µs

'mekrgobq fm gzzgm fqbogrke m'

Còn việc tốn thì các bạn đo bằng gì để biết nó tốn?

1 Like
#19

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 :joy:

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 đó :joy:

1 Like
#20

Theo bạn thì mất bao lâu?

%%time
make_palindrome('a b c d c d e f e a b c c c c')

CPU times: user 377 ms, sys: 0 ns, total: 377 ms
Wall time: 376 ms

'a b c d c e c f c e c d c b a'
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?