Description
In this problem, you're asked to sort some strings by how close it is to a palindrome (a string that reads the same from left and right). A string has greater distance (to becoming a palindrome) if it requires more changes: replacing a character in the string with any other character.
For example: string "gggg" is already a palindrome, thus the distance is 0, while string "ow" has distance 1 (you can replace the 'o' with 'w' to make it a palindrome), and "ggy" also has distance 1.
Given N strings, sort them by their distances ascendingly. If two strings have the same distances, compare them alphabetically(*). It is guaranteed that all strings in one input file are distinct.
weakpal is a class which has two member data: str (of type c++ std::string, the original string), dis (the distance). The container to store the "weakpal"s is a binary search tree (BST), in which each node contains a pointer to a weakpal object.
You need to implement the following functions in class weakpal:
1. setStr(string)
2. setDis()
3. operator<(weakpal): comparing two weakpal objects, obviously needed for implementing BST insert.
You also need to implement the function BST::insertNode(string), which inserts a weakpal to the BST based on the input string.
*Alphabetical order (by Wikipedia's explanation): To determine which of two strings of characters comes first when arranging in alphabetical order, their first letters are compared. If they differ, then the string whose first letter comes earlier in the alphabet comes before the other string. If the first letters are the same, then the second letters are compared, and so on. If a position is reached where one string has no more letters to compare while the other does, then the first (shorter) string is deemed to come first in alphabetical order.
Input
Input format:
N
S_1
S_2
...
S_N
Input constraints:
1 <= N <= 1000
The length of every string will not exceed 20. Every string is distinct.
Output
S_sorted_1
S_sorted_2
...
S_sorted_N
(Print the strings in separate lines, sorted as requested in the problem description.)
Partial Judge Code
12789.cpp
Partial Judge Header
12789.h
Tags