Xâu khả đối xứng

**lehang_gb1** · 22-07-2009 22:15

Nhập vào 1 xâu, kiểm tra xem xâu có đối xứng hay không? Nếu không đối xứng, kiểm tra xem xâu có khả đối xứng hay không? (Xâu khả đối xứng là xâu nếu thay đổi vị trí 1 số kí tự thì thành xâu đối xứng). Nếu xâu là khả đối xứng, đổi vị trí 1 số kí tự để được xâu đối xứng.

**quangtq** · 22-07-2009 22:40

Chưa nghĩ ra cách. Vét thì lâu quá.

**bld** · 23-07-2009 08:11

kt đối xứng thì dễ rồi
còn thêm vào 1 số kí tự thì mình chỉ làm dc bài thêm vào 1 số kí tự ít nhất đề xâu đối xứng thôi , (khác nhau chỗ ít nhất ) , nếu ko bắt buộc ít nhất thì có thể thuật toán đơn giản hơn , để nghĩ xem
còn việc thêm vào ít nhất thì bạn tìm xâu đối xứng dài nhất , rồi dựa vào xâu đó dể thêm

**ngtrhieu0011** · 23-07-2009 08:20

kt đối xứng = vét O(N)
kt khả năng đối xứng: đếm số ký tự mỗi loại, nếu tất cả là chẵn hoặc chỉ có 1 lẻ thì có khả năg.

Vd: abbcadd
số ký tự a: 2
số ký tự b: 2
số ký tự c: 1
số ký tự d: 2
=> có khả năng đối xứng

**bld** · 23-07-2009 09:17

Được gửi bởi ngtrhieu0011

kt đối xứng = vét O(N)
kt khả năng đối xứng: đếm số ký tự mỗi loại, nếu tất cả là chẵn hoặc chỉ có 1 lẻ thì có khả năg.

Vd: abbcadd
số ký tự a: 2
số ký tự b: 2
số ký tự c: 1
số ký tự d: 2
=> có khả năng đối xứng

hay hay ^^ thumb up!
nhưng mà tóm lại thì chỉ cần có 1 kí tự xuất hiện 2 lần là đủ để đối xừng rồi , quan trọng là bước thêm vào

**lehang_gb1** · 23-07-2009 11:48

không được thêm kí tự vào mà chỉ chuyển vị trí của chúng thôi bld, mình có ý tưởng như của hieu

**bld** · 23-07-2009 11:50

à đúng rồi ,ko đọc kỉ đề ;p vậy thì việc chuyển cũng dễ dàng thôi

**quangtq** · 23-07-2009 15:50

Chuyển tương đương với thêm vào mới và xóa cũ mà.
Vậy thì có thể như sau:
1. Kt đối xứng
2. Kt khả đối xứng
3. Nếu khả đối xứng, QHĐ để tìm số kí tự ít nhất cần thêm vào tạo thành xâu đối xứng.
4. Truy vết in kq