10 lines solutions for c++


  • 6
    S

    I think there is no need to sort the dic, just iterate the dic and test whether the word is satisfied and whether we need update our answer.

        string findLongestWord(string s, vector<string>& d) {
            string ans;
            for (int i = 0; i < d.size(); i++) {
                int pi = 0, pj = 0;
                for (; pi < s.size() && pj < d[i].size(); pi++) {
                    pj += s[pi] == d[i][pj];
                }
                if (pj == d[i].size() && (ans.size() < d[i].size() || (ans.size() == d[i].size() && ans > d[i])))
                    ans = d[i];
            }
            return ans;
        }
    

  • 1
    F

    very brilliant


  • 0
    F

    The answer is So great !Thanks for sharing


  • 0
    A

    brilliant but unfortunately not readable


  • 0
    Z

    @saxion The value of "sort", we can traverse from back to front, and we can end the loop early.


  • 0

    @saxion GREAT SOLUTION! I rewrote it here, I hope you don't mind.
    @abdallahmahran I rewrote it here with comments, I hope it helps!

    string findLongestWord(string s, vector<string>& d) {
            string ans;
            for(string word: d){ //for each word in d 
                int j=0,k=0;
                while(j<s.size() && k<word.size()){ 
                    if(s[j]==word[k]) //for each letter in s and word, compare
                        k++;         // & increment only if they equal
                    j++;   
                }
                int n=word.size();
                if(k==n && ((ans.size()==n && ans>word) || ans.size()<n))
                    ans=word;
                //save word as ans if the three conditions are met: 
                    //1. k==n: if every letter of word exists in string s (and in order of the word)
                    //2. ans.size()<n: word is a longer word than ans 
                    //3. (ans.size()==n && ans>word): word is same size as ans but is lexicographically smaller
                //REMEMBER: "return the longest word with the smallest lexicographical order."
            }
            return ans;
        }
    

  • 0
    T

    I think you can use ans = std::move(d[i]) to further improve the performance if d is not const, just a nit.


  • 0
    T

    @zachluna maybe for (string& word : d) is better?


Log in to reply
 

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