Python Simple (Two pointer)


  • 10

    Let's check whether each word is a subsequence of S individually by "best" order (largest size, then lexicographically smallest.) Then if we find a match, we know the word being considered must be the best possible answer, since better answers were already considered beforehand.

    Let's figure out how to check if a needle (word) is a subsequence of a haystack (S). This is a classic problem with the following solution: walk through S, keeping track of the position (i) of the needle that indicates that word[i:] still remains to be matched to S at this point in time. Whenever word[i] matches the current character in S, we only have to match word[i+1:], so we increment i. At the end of this process, i == len(word) if and only if we've matched every character in word to some character in S in order of our walk.

    def findLongestWord(self, S, D):
        D.sort(key = lambda x: (-len(x), x))
        for word in D:
            i = 0
            for c in S:
                if i < len(word) and word[i] == c:
                    i += 1
            if i == len(word):
                return word
        return ""
    

  • 0
    Z

    Thanks for your elegant solution!


  • 0

    Thank you for your solution, very helpful!


  • 3

    The same idea using python build-in function:

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

  • 1
    G

    Thanks for a simple and easy-to-understand explanation! Sometimes other people are so good and post answers that are super short/hard-to-understand. Thanks for keeping it real.


  • 0
    S

    Here is my naive implementation

    class Solution(object):
        def findLongestWord(self, s, d):
            """
            :type s: str
            :type d: List[str]
            :rtype: str
            """
            def is_subsequence(s,t):
                # check if t is subsequence of s
                i = 0
                j = 0
                
                m = len(s)
                n = len(t)
                
                if n > m:
                    return False
                
                while i < m and j < n:
                    if s[i] == t[j]:
                        i += 1
                        j += 1
                    else:
                        i += 1
                return j == n
                
            subsequence_length = 0
            subsequence = ''
            for string in d:
                if is_subsequence(s,string):
                    if subsequence_length < len(string):
                        subsequence = string
                        subsequence_length = len(string)
                    elif subsequence_length == len(string):
                        subsequence = min(subsequence,string)
            return subsequence

  • 0
    S

    great solution!


Log in to reply
 

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