My AC approach using sorting and binary search


  • 2
    E

    Approach:

    1. Sort the strings in descending order of length (if length is equal, opt for the lexicographically smaller one)

    2. Pre-process the string s into a dictionary of char to list of indices. Note that these indices are in sorted order and can therefore facilitate the use of binary search.

    Overall Time complexity for N strings of average length |T| and string of length |S| :O(NlogN) + O(NTlog(|S|)

    class Solution {
    public:
        struct order
        {
            bool operator()(const string& s1, const string& s2)
            {
                if(s1.size() == s2.size())
                {
                    int j = 0;
                    while(s1[j] == s2[j] && j < s1.size())
                        j++;
                    return (j == s1.size()) ? true : s1[j] < s2[j];
                }
                else
                    return s1.size() > s2.size();
            }
        };
        string findLongestWord(string s, vector<string>& d)
        {
            sort(d.begin(), d.end(), order());
            vector<vector<int>> dict(26, vector<int>());
            int i = 0;
            for(auto c : s)
                dict[c - 'a'].push_back(i++);
            string result;
            for(auto ele : d)
            {
                int id = 0;
                bool notPossible = false;
                for(auto c : ele)
                {
                    auto nextIt = lower_bound(dict[c - 'a'].begin(), dict[c - 'a'].end(), id);
                    if(nextIt == dict[c - 'a'].end())
                    {
                        notPossible = true;
                        break;
                    }
                    id = *nextIt + 1;
                }
                if(!notPossible)
                {
                    result = ele;
                    break;
                }
            }
            return result;
        }
    };
    

  • 0
    M

    I think the overall complexity of N strings is O(N^2*log|S|)


  • 0
    E

    @moan1223 thanks, fixed it.


  • 0
    K

    Shorter one with same approach binary search:

    bool comp(string &a, string &b) {
        if (a.size()==b.size()) return a.compare(b)<0;
        return a.size()>=b.size();
    }
    
    class Solution {
    public:
        string findLongestWord(string s, vector<string>& d) {
            string res;
            
            vector<vector<int>> index(26);
            for(int i=0; i<s.size(); ++i) index[s[i]-'a'].push_back(i);
            
            for(auto &t : d) {
                if (ok(t, index)) {
                    if (res.empty()||comp(t,res)) res = t;
                }
            }
            
            return res;
        }
        
        bool ok(string t, vector<vector<int>> &index) {
            int cur = -1;
            for(char &c : t) {
                auto is = index[c-'a'];
                auto i = upper_bound(is.begin(), is.end(), cur);
                if (i==is.end()) return false;
                cur = *i;
            }
            
            return true;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.