thinhdu
BAN USERSince the requirement is O(1) look up only, we can use a hash table to store all possible combination for each string. For each string, insert all possible combination as follow
void addString(string& str, unordered_map<string,int>& m)
{
//cout << str << endl;
m.insert(pair(str, 1));
int len = str.length();
for (int i = 0; i < len; ++i)
{
char c = str[i];
str[i] = '*';
//cout << str << endl;
m.insert(pair(str, 1));
str[i] = c;
}
for (int i = 2; i <= len; ++i)
{
for (int j = 0; j < len-(i-1); ++j)
{
string tmp = str;
for (int k = j; k < j+i-1; ++k)
{
tmp[k] = '*';
}
for (int k = j+i-1; k < len; ++k)
{
char c = tmp[k];
tmp[k] = '*';
//cout << tmp << endl;
m.insert(pair(tmp, 1));
tmp[k] = c;
}
}
}
}
Node * convert(Node * root)
{
if (root == NULL)
return root;
Node *left = convert(root->left);
if (left)
{
while (left->right)
{
left = left->right;
}
left->right = root;
root->left = left;
}
Node *right = convert(root->right);
if (right)
{
while (right->left)
{
right = right->left;
}
right->left = root;
root->right = right;
}
return root;
}
Node * treeToList(Node* root)
{
Node *head = convert(root);
Node *tail = head;
if (!head)
return NULL;
while (head->left || tail->right)
{
if (head->left) head = head->left;
if (tail->right) tail = tail->right;
}
head->left = tail;
tail->right = head;
return head;
}
Simple O(n) time, O(n) memory
- thinhdu March 24, 2015