Tìm các từ hoán vị trong 1 chuỗi


(Bi) #1

Chào các bác, các bác giúp em với. Em mới nhập môn nên hơi gà mờ.

Làm sao để Output ra tất cả các từ hoán vị trong 1 chuỗi.

Input Output
“list arm Six Xis silt ram list tills” list = silt
list = list
arm = ram
silt = list

(明玉) #2

Cho một pool với key-value type là: <string, string[]>
list và silt là hoán vị của nhau, vì vậy nếu ta sắp xếp các kí tự của 2 string này thì đều sẽ cho ra 1 string là ilst, dùng string này làm key và đưa item đang xét trong input vào pool.
Như vậy, chuỗi kia có list, silt, list thì sau khi quét cả input, trong pool sẽ tồn tại 1 mục là:

pool['ilst'] = ['list', 'silt', 'list']

Tương tự cho các item còn lại trong input, sau khi xây dựng xong pool, việc còn lại là ngồi thống kê dữ liệu trong pool. Hoặc có thể vừa duyệt input vừa thống kê luôn để tiết kiệm thời gian chạy.
Ngắn gọn là: ta ngồi “băm” (hash) tất cả item trong input để dồn hết vào các nhóm hoán vị.

Nói đi nói lại, mới nhập môn thì bài này là quá khó.


(SITUVN.gcd) #3

Các kí tự của các từ có tần suất bằng nhau thì đó là hoán vị của nhau.


(rogp10) #4

Tức là đưa về dạng chuẩn đó mà :slight_smile: sau này thớt sẽ cần.


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