Short Python solutions


  • 14
    def findLongestWord(self, s, d):
        def isSubsequence(x):
            it = iter(s)
            return all(c in it for c in x)
        return max(sorted(filter(isSubsequence, d)) + [''], key=len)
    

    More efficient version (no sorting):

    def findLongestWord(self, s, d):
        def isSubsequence(x):
            it = iter(s)
            return all(c in it for c in x)
        return min(filter(isSubsequence, d) + [''], key=lambda x: (-len(x), x))
    

    Different style:

    def findLongestWord(self, s, d):
        best = ''
        for x in d:
            if (-len(x), x) < (-len(best), best):
                it = iter(s)
                if all(c in it for c in x):
                    best = x
        return best
    

    Optimized as suggested by @easton042, testing from longest to shortest and returning the first valid one without testing the rest:

    def findLongestWord(self, s, d):
        def isSubsequence(x):
            it = iter(s)
            return all(c in it for c in x)
        d.sort(key=lambda x: (-len(x), x))
        return next(itertools.ifilter(isSubsequence, d), '')
    

    Or:

    def findLongestWord(self, s, d):
        for x in sorted(d, key=lambda x: (-len(x), x)):
            it = iter(s)
            if all(c in it for c in x):
                return x
        return ''
    

    And taking that even further by not sorting unnecessarily much:

    def findLongestWord(self, s, d):
        heap = [(-len(word), word) for word in d]
        heapq.heapify(heap)
        while heap:
            word = heapq.heappop(heap)[1]
            it = iter(s)
            if all(c in it for c in word):
                return word
        return ''

  • 3

    @StefanPochmann Your code is always mind blowing...


  • 0

    Here's something a little different. You can build a 2D map of the input string which maps at each index characters 'a' - 'z' pointing to the next occurrence of that char. Then test each string in the dictionary using the map to skip to the next char. I use -1 to denote that there is no next char. If you get through the dictionary word without hitting a -1 that dictionary word is valid. I didn't sort the dictionary but you could, I just check each word and pick the best.

        public string FindLongestWord(string s, IList<string> d) 
        {
            int[,] map = new int[s.Length+1, 26];
            for (int col = 0; col < 26; col++) map[s.Length,col] = -1;
            
            for (int i = s.Length - 1; i >= 0; i--)
            {
                for (int col = 0; col < 26; col++)
                {
                    map[i,col] = map[i+1,col];
                }
                map[i, s[i]-'a'] = i+1;
            }
            
            string best = "";
            foreach (string x in d)
            {
                if (x.Length < best.Length) continue;
    
                int dIndex = 0;
                foreach (char c in x)
                {
                    dIndex = map[dIndex,c-'a'];
                    if (dIndex == -1) break;
                }
                
                if (dIndex != -1)
                {
                    if (x.Length > best.Length || (x.Length == best.Length && string.Compare(x, best) == -1)) best = x;
                }
            }
            
            return best;
        }
    

  • 1

    For the sake of performance, you can filter from the longest string and return before testing all strings.


  • 9

    Some comments:

    • The built-in function iter() takes an iterable object and returns an iterator.
    • with state that remembers where it is during iteration,
    • c in it returns True if the value in the iteration and updates the state to point at the next value
    • return False when it goes to the end of iteration

    just for those who are not familiar with iter() at first like me.


  • 0

    @easton042 Right, thanks. I just added two solutions that do that.


  • 1

    I love the last solution.
    But the second from last doesn't seem working as wish, I guess you mean this:
    return next(ifilter(isSubsequence, d), '')


  • 0

    @easton042 What do you mean "doesn't seem working as wish"? It works for me and it does get accepted.


  • 2

    return next(iter(filter(isSubsequence, d)), '')
    this statement in face applies isSubsequence to every element of d, instead of only finds out the first one that can pass the test. So I think the right way to iterate is like this:
    return next(ifilter(isSubsequence, d), '')


  • 1

    @easton042 Oh wow, that is embarrassing. You're right, using filter was nonsense. And I just mindlessly wrapped iter around it because Python complained without it. I should've turned on my brain instead. Sorry I got that wrong, I replaced it with itertools.ifilter now. And added a not-so-functional version as well.


  • 0

    Hi @StefanPochmann, Thanks for your solution. I see several of your answers using the function isSubsequence. Could you spend some time explain the logic of this function here? Especially why we need it = iter(s). I am confused about why we need to convert s to an iterator each time I see the function used for solving different problems. Thanks in advance.


  • 0

    @0x0101 Because while I'm going through x, I want to go through s only once. Overall. If I used s directly, I'd search through s from its start for every character in x. Which is wrong.


  • 0
    W

    I really like this elegant line, thanks again!

    (-len(x), x) < (-len(best), best)
    

Log in to reply
 

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