Python: Find the longest word in set of words which is a subsequence of a given string

Last update on December 21 2024 07:19:38 (UTC/GMT +8 hours)

Longest Subsequence Word

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence (A,B,D) is a subsequence of (A,B,C,D,E,F) obtained after removal of elements C, E, and F. The relation of one sequence being the subsequence of another is a preorder.
The subsequence should not be confused with substring (A,B,C,D) which can be derived from the above string (A,B,C,D,E,F) by deleting substring (E,F). The substring is a refinement of the subsequence.
The list of all subsequences for the word "apple" would be "a", "ap", "al", "ae", "app", "apl", "ape", "ale", "appl", "appe", "aple", "apple", "p", "pp", "pl", "pe", "ppl", "ppe", "ple", "pple", "l", "le", "e", "".
Write a Python program to find the longest word in a set of words which is a subsequence of a given string.

Sample Solution:

Python Code:

# Function to find the longest word sequence from a set of words in a given string
def longest_word_sequence(s, d):
    long_word = ""  # Variable to store the longest word sequence
    
    for word in d:  # Iterate through each word in the set
        temp_word = ''  # Variable to store the current word sequence
        j = 0  # Index to track the position in the string 's'
        
        for letter in word:  # Iterate through each letter in the current word
            for i in range(j, len(s)):  # Iterate through the string 's' starting from index 'j'
                if letter == s[i]:  # If the letter is found in the string
                    temp_word += letter  # Add the letter to the current word sequence
                    j = i  # Update the index to the position of the found letter
                    break
                else:
                    continue  # Continue searching for the letter if not found in the current position
            
        # Check if the current word sequence is equal to the word and longer than the current longest word
        if temp_word == word and len(long_word) < len(temp_word):
            long_word = temp_word  # Update the longest word sequence
    
    return long_word  # Return the longest word sequence found

# Test cases
print(longest_word_sequence("Green", {"Gn", "Gren", "ree", "en"}))
print(longest_word_sequence("pythonexercises", {"py", "ex", "exercises"}))

Sample Output:

Gren
exercises

Explanation:

Here is a breakdown of the above Python code:

• Define a function named "longest_word_sequence()" that takes a string 's' and 'a' set of words 'd' as input.
• Initialize a variable 'long_word' to store the longest word sequence found.
• Use nested loops to iterate through each word in the set and each letter in the word.
• Check if the letter is present in the string 's' and build the current word sequence (temp_word).
• Compare the current word sequence with the word itself. If they match and the current word sequence is longer than the current longest word, update 'long_word'.
• Return the longest word sequence found.
• Test the function with different inputs to check its functionality.

Visual Presentation:

Flowchart:

Python Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Given a list of numbers and a number k, write a Python program to check whether the sum of any two numbers from the list is equal to k or not.
Next: Write a Python program to check whether a number is "happy" or not.