Given a long word with N non-unique characters, we know there can be 2^N abbreviations (including the original word, and including the empty string).
Requirement: I give you a list of strings and you suspect some of them could be an abbreviation of your word. Find the longest string among them that’s a valid abbreviation. Optimize for time complexity.
I feel this problem appears simple but not easy to complete quickly
https://github.com/tiger40490/repo1/blob/py1/py/str/testAbbr_ez.py is my python solution, different from the c++ solution below. Not sure which has more bugs.
I started with string::find() and hit the problem of non-unique characters. Interviewer hinted char-matching — the key point I needed for this type of problem.
#include <iostream> #include <algorithm> #include <vector> using namespace std; typedef string candidate; vector<candidate> v{"monkey","aaaaaaaaaaaaaaaaaa", "mamalon", "monk"}; string const haystack{"mamalonkey"}; size_t hsize=haystack.size(); //Tip: can use typdef alias in argument:) bool lenComp(candidate const & a, candidate const & b){ return a.size()<=b.size(); } ostream & operator<<(ostream & os, vector<candidate> const & c){ size_t const sz = c.size(); for (int i=0;i<sz; ++i){ os<<c[i]<<" "; } os<<endl; return os; } //single-pass 🙂 } bool check1candate(candidate const & c){ if (c.size() > hsize) return false; for(int i=0, h=0; h<hsize; ++h){ if (c[i] == haystack[h]){ if (i==c.size()-1) return true; ++i; } } return false; } int main(){ sort(v.begin(), v.end(), lenComp); cout<<v; for (int i=v.size()-1; i>=0; --i){ if (check1candate(v[i])){ cout<<"winner is "<<v[i]; return 0; } } }