eitanbenamos
BAN USER
a linear time solution
---------------------------
* can we check the word from the map without scanning the whole input string (which might be order of magnitude longer) ?
* assume w is word from map, str is input.
* if we could go from the w[k] to the w[k+1] on the input string in O(1), that would fix it all.
* we can do that with pre-processing of the input string into a matrix.
* row per character in alphabet, so 256 rows.
* column per character
* pre-processing:
* for each character (c) of input string in index K, we mark it in the map @ [c,k].
* we also scan the row towards column 0 until we hit another occurrence of that character. for every column we scanned, we find the letter & point from it to the column in which c appears.
* this ensures that from a given offset, we can get the offset of any other character in O(1)
* the preprocessing time is O(256 * input string) which is linear time, although actual constant would rarely be that large.
#include <string>
#include <array>
#include <vector>
#include <unordered_set>
#include <cassert>
using namespace std;
#define NUM_MAT_ROWS 256
typedef unordered_set<string> map_t;
typedef array<size_t, NUM_MAT_ROWS> per_char_info_t;
struct input_char_next {
per_char_info_t next; // point to the next offset of character 'c' at offset 'c'.
input_char_next()
{
fill(next.begin(), next.end(), -1/*poison => no such character in higher offset*/);
}
};
typedef vector<input_char_next> input_md_t; // lookup information per character input string
class my_algorithm {
protected:
input_md_t str_lookup;
size_t n_col; // No. of matrix columns
void prepare_matrix(const string &str)
{
for (int offset = 0; offset < str.size(); ++offset) {
char ch = str[offset];
struct input_char_next &elem = str_lookup[offset];
// initialize pointing from previous characters to this one
ssize_t prev = offset;
do {
prev--;
struct input_char_next &pre = str_lookup[prev];
pre.next[ch] = offset;
} while ((prev >= 0) && (str[prev] != ch));
}
}
public:
my_algorithm()
{}
const string *
find_longest_dict_word_by_del_from_input(const string &str,
const map_t &map)
{
const string *res = nullptr;
// preprocessing
n_col = str.size();
str_lookup.resize(str.size());
prepare_matrix(str);
for (auto wit = map.begin(); wit != map.end(); ++wit) {
if (wit->size() == 0) {
continue; // not sure what to do with empty string - they can always be matched :)
}
const string &w = *wit; // this is the word we attempt to match in the input string
char first_ch = w[0];
size_t curr_offset = (first_ch == str[0]) ? 0 : str_lookup[0].next[first_ch]; // offset with which we move forward on input string as we match characters.
auto cit = w.begin();
for (++cit; (cit != w.end()) && (curr_offset != -1); ++cit) {
curr_offset = str_lookup[curr_offset].next[*cit];
}
if (curr_offset != -1) {
// the word can be made from input string - check if its longer than what we already found
if (!res || (w.size() > res->size())) {
res = &w; // we found a longer match
}
}
}
return res;
}
};
int main ()
{
my_algorithm alg;
const string *res;
{ // map is empty
const map_t map;
res = alg.find_longest_dict_word_by_del_from_input("abpcplea", map);
assert(res == nullptr);
}
{ // input string is empty
const map_t map = {"eitan"};
res = alg.find_longest_dict_word_by_del_from_input("", map);
assert(res == nullptr);
}
{
const map_t map = {"ale", "apple", "monkey", "plea"};
res = alg.find_longest_dict_word_by_del_from_input("abpcplea", map);
assert(*res == "apple");
}
{ // longest match isnt first & is also on end of input string
const map_t map = {"ale", "apple", "monkey", "plea"};
res = alg.find_longest_dict_word_by_del_from_input("abpcpleamonkey", map);
assert(*res == "monkey");
}
return 0;
}
push all edges into a map - the key represent both items, as a pair.
now iterate over map & for each element, search the reverse in the same map.
if its found, we have the reverse.
overall runtime is linear time bcz map is O(1) per operation.
scan is on map so it naturally eliminates duplicates from input - bcz these are eliminated when we push them to the map (unique key)
Repchristinetcollazoc, Software Analyst
I am a pediatric nurse.I administer directly procedures and medicines to children according to prescribed I also continually assess ...
Repjoycejflora, Android Engineer at ABC TECH SUPPORT
I am excited about cooperation and interesting projects. Last year I work for a person who provides the black magic ...
RepKimRPierce, Employee at Achieve Internet
I am a customer service-oriented Travel Agent in Travel and Tourism industries. I strongly believe that the skills and abilities ...
RepDonnaWHale, Data Engineer at ADP
Hi, I am passionate writer with a BA in English from the Ohio State University.5+ years of experience writing ...
Rephoychrista, Blockchain Developer at ASU
Worked with Clients to guide them through the event details about copier leasing companies and served as their personal coordinator ...
Repjonej8821, Blockchain Developer at Alliance Global Servies
I am EbonyTuckson .I am a teacher who works in High school. I work during school hours but may also ...
Repharoldknopph, Android test engineer at AMD
I am a publicity writer from Atlanta USA . I create an intended public image for individuals, groups, or organizations. I ...
Repthonylermat, OOPS Experienced at 247quickbookshelp
I have been assigned based on the successful candidate's level of training and experience but will include types of ...
RepEviePaul, Member Technical Staff at Abs india pvt. ltd.
I am a Studio camera operator from Florida USA.I love to relax n' chill. love when it's cloudy ...
the 2 data structures are a list (for O(n) insertion) & a hash-map that keys the list elements.
- eitanbenamos March 31, 2018insert requires a list traversal bcz hashmap doesnt maintain ordering, so we cannot search an adjacent item.
once we insert the item into the list, we update the hash-map so a lookup will yield the pointer to that object.
delete requires lookup using hash-map (O(1), followed by the removal of entry from hash-map (O(1) & then unlink of object from list (O(1)