Cho một văn bản, chuyển đổi nó thành một palindrome với bổ sung tối thiểu của các chữ cái để nó

Question

Đây là một câu hỏi phỏng vấn khá thú vị:

Cho một từ, thêm số lượng ít nhất của các chữ cái với nó để chuyển đổi nó thành một palindrome.

Ví dụ: nếu "hello" là chuỗi được cung cấp, kết quả phải là "hellolleh". Nếu "coco" được cho, kết quả sẽ là "cococ".

Một cách tiếp cận tôi có thể nghĩ đến là nối thêm chuỗi ngược vào cuối chuỗi gốc, sau đó cố gắng loại bỏ các ký tự thừa từ cuối. Tuy nhiên, tôi không thể tìm ra cách để làm điều này một cách hiệu quả. Có ai có ý tưởng nào?

Answer 1

Trước tiên hãy tạo một hàm để kiểm tra chuỗi cho palindrome-ness, hãy nhớ rằng "a" và "aa" là palindromes. Họ là palindromes, phải không ???

Nếu đầu vào là palindrome, trả về (0 ký tự cần thêm) Lặp từ x [length] xuống x [1] kiểm tra xem tập hợp con của chuỗi x [i] .. x [length ] là một palindrome, để tìm palindrome dài nhất.

Lấy chuỗi con từ chuỗi đầu vào trước palindrome dài nhất, đảo ngược nó và thêm nó vào cuối sẽ làm palindrome ngắn nhất thông qua nối thêm.

dừa => c + OCO => c + OCO + c

mmmeep => mmmee + p => mmmee + p + eemmm

Answer 2

OK! Đây là nỗ lực thứ hai của tôi.

Ý tưởng là chúng tôi muốn tìm xem có bao nhiêu ký tự ở cuối chuỗi có thể được sử dụng lại khi thêm các ký tự thừa để hoàn thành palindrome. Để thực hiện điều này, chúng tôi sẽ sử dụng một sửa đổi của thuật toán kết hợp chuỗi KMP. Sử dụng KMP, chúng tôi tìm kiếm chuỗi gốc để đảo ngược. Khi chúng ta đến cuối của chuỗi, chúng ta sẽ có nhiều kết hợp nhất có thể giữa chuỗi đảo ngược và chuỗi gốc xuất hiện ở cuối chuỗi. Ví dụ:

HELLO 
    O 

1010 
010 

3202 
202 

1001 
1001 

Tại thời điểm này, KMP thường nói "không khớp" trừ khi chuỗi gốc là palindrome. Tuy nhiên, vì chúng tôi hiện biết số lượng của chuỗi đảo ngược được so khớp, chúng tôi có thể tìm ra số lượng ký tự còn thiếu và sau đó gắn chúng vào cuối chuỗi. Trong trường hợp đầu tiên, chúng tôi đang thiếu LLEH. Trong trường hợp thứ hai, chúng tôi thiếu 1. Trong lần thứ ba, chúng tôi đang thiếu 3. Trong trường hợp cuối cùng, chúng ta không bỏ sót bất cứ điều gì, vì chuỗi ban đầu là một palindrome.

Thời gian chạy của thuật toán này là thời gian chạy của tìm kiếm KMP chuẩn cộng với thời gian cần thiết để đảo ngược chuỗi: O (n) + O (n) = O (n).

Vì vậy, bây giờ để tranh luận tính chính xác. Điều này sẽ đòi hỏi một số nỗ lực. Xem xét câu trả lời tối ưu:

| original string | | extra characters | 

Giả sử chúng ta đọc ngược từ cuối, có nghĩa là chúng ta sẽ đọc ít nhất ngược lại của chuỗi gốc. Một phần của chuỗi đảo ngược này mở rộng ngược vào phần thân của chuỗi gốc. Trong thực tế, để giảm thiểu số lượng ký tự được thêm vào, đây phải là số ký tự lớn nhất có thể kết thúc lại vào chính chuỗi đó. Chúng ta có thể thấy điều này tại đây:

| original string | | extra characters | 
      | overlap | 

Bây giờ, điều gì xảy ra trong bước KMP của chúng tôi? Vâng, khi tìm kiếm đảo ngược của chuỗi bên trong chính nó, KMP sẽ giữ càng lâu của một trận đấu càng tốt ở tất cả các lần như nó hoạt động trên chuỗi. Điều này có nghĩa là khi KMP chạm vào cuối chuỗi, phần khớp mà nó duy trì sẽ là kết quả dài nhất có thể, vì KMP chỉ di chuyển điểm bắt đầu của kết quả ứng cử viên về phía trước trên một lỗi. Do đó, chúng tôi có chồng chéo dài nhất có thể, vì vậy chúng tôi sẽ nhận được số ký tự ngắn nhất có thể được yêu cầu ở cuối.

Tôi không chắc chắn 100% tính năng này hoạt động, nhưng có vẻ như nó hoạt động trong mọi trường hợp tôi có thể ném vào nó. Bằng chứng chính xác có vẻ hợp lý, nhưng nó hơi lộn xộn một chút bởi vì bằng chứng dựa trên KMP chính thức có lẽ sẽ hơi phức tạp một chút.

Hy vọng điều này sẽ hữu ích!

Answer 3

Để trả lời tôi sẽ áp dụng cách ngây thơ này:

1. khi chúng tôi cần 0 ký tự? khi chuỗi đó là palindrome
2. khi chúng ta cần 1 ký tự? khi ngoại trừ chuỗi ký tự đầu tiên là palindrome
3. khi chúng ta cần 2 ký tự? khi trừ các nhân vật 2 đầu chuỗi là một palindrome
4. etc etc ...

Vì vậy, một thuật toán có thể là

for index from 1 to length 
    if string.right(index) is palindrome 
    return string + reverse(string.left(index)) 
    end 
    next 

chỉnh sửa

Tôi không nhiều một Python guy, nhưng một thực hiện đơn giản minded của mã giả ở trên có thể là

>>> def rev(s): return s[::-1] 
... 
>>> def pal(s): return s==rev(s) 
... 
>>> def mpal(s): 
... for i in range(0,len(s)): 
... if pal(s[i:]): return s+rev(s[:i]) 
... 
>>> mpal("cdefedcba") 
'cdefedcbabcdefedc' 
>>> pal(mpal("cdefedcba")) 
True 

Answer 4

Giải pháp thời gian tuyến tính đơn giản.

Hãy gọi chuỗi của chúng tôi S.

Hãy f (X, P) là chiều dài của tiền tố chung dài nhất của X và P. Tính f (S [0], rev (S)), f (S [1], rev (S)), ... trong đó S [k] là hậu tố của S bắt đầu từ vị trí k. Rõ ràng, bạn muốn chọn k tối thiểu sao cho k + f (S [k], rev (S)) = len (S). Điều đó có nghĩa là bạn chỉ cần thêm ký tự k vào cuối. Nếu k bằng 0, sting đã là palindrom. Nếu k = len (S), thì bạn cần nối thêm toàn bộ ngược lại.

Chúng tôi cần tính toán f (S [i], P) cho tất cả S [i] một cách nhanh chóng. Đây là phần khó khăn. Tạo một cây hậu tố của S. Traverse cây và cập nhật mọi nút với độ dài của tiền tố chung dài nhất với P. Các giá trị tại các lá tương ứng với f (S [i], P).