Python开发：判断单词列表是否按序存在于字符串并返回最长有序子列表

Alright, let's solve this problem step by step. The goal is to check if a list of words appears in order in a target string (as a subsequence), and if not, find the longest consecutive sublists from the original word list that do appear in order.

Approach #

1. Preprocess the Target String: First, we'll clean the target string by splitting it into words and removing any leading/trailing punctuation (like periods or commas). We'll also convert everything to lowercase for case-insensitive matching (since "Street" and "street" should count as a match).
2. Check Consecutive Sublists: For each starting index in the input word list, we'll find the longest consecutive sublist starting at that index where each word appears in the target string in the same order (i.e., each subsequent word in the sublist comes after the previous one in the target).
3. Track Longest Sublists: We'll keep track of the longest valid sublists found, and return all of them if there are multiple with the same maximum length.

Solution Code #

def find_longest_ordered_sublists(target_str, word_list):
    def clean_word(word):
        """Remove common punctuation from start/end and convert to lowercase"""
        return word.strip('.,!?;:"\'()[]{}').lower()
    
    # Preprocess target into a list of cleaned, lowercase words
    target_words = [clean_word(word) for word in target_str.split()]
    num_words = len(word_list)
    
    if num_words == 0:
        return []
    
    max_length = 0
    candidates = []
    
    for start_idx in range(num_words):
        current_target_pos = 0
        end_idx = start_idx
        
        # Find the first occurrence of the starting word in the target
        start_word = clean_word(word_list[start_idx])
        found_start = False
        for pos in range(current_target_pos, len(target_words)):
            if target_words[pos] == start_word:
                current_target_pos = pos + 1
                found_start = True
                break
        
        if not found_start:
            continue  # Skip this starting index if the word isn't in the target
        
        # Extend the sublist as far as possible
        for next_idx in range(start_idx + 1, num_words):
            next_word = clean_word(word_list[next_idx])
            found_next = False
            for pos in range(current_target_pos, len(target_words)):
                if target_words[pos] == next_word:
                    current_target_pos = pos + 1
                    end_idx = next_idx
                    found_next = True
                    break
            
            if not found_next:
                break  # Can't extend further, move to next starting index
        
        # Update our tracking variables
        sublist_length = end_idx - start_idx + 1
        current_sublist = word_list[start_idx:end_idx + 1]
        
        if sublist_length > max_length:
            max_length = sublist_length
            candidates = [current_sublist]
        elif sublist_length == max_length:
            candidates.append(current_sublist)
    
    # Remove duplicate sublists (in case of overlapping or identical entries)
    unique_candidates = []
    seen = set()
    for sublist in candidates:
        sublist_tuple = tuple(sublist)
        if sublist_tuple not in seen:
            seen.add(sublist_tuple)
            unique_candidates.append(sublist)
    
    # If the entire list is valid, return it as the only candidate
    if max_length == num_words:
        return [word_list]
    else:
        return unique_candidates

Example Usage #

Let's test this with a corrected version of your example (since the original example's expected output doesn't align with the given word list and target string):

Target String: 'The boy was walking his big dog down the street.'
Word List: ['boy', 'was', 'his', 'dog', 'down', 'the', 'street']

Running the function:

target = 'The boy was walking his big dog down the street.'
words = ['boy', 'was', 'his', 'dog', 'down', 'the', 'street']
print(find_longest_ordered_sublists(target, words))

Output:

[['boy', 'was', 'his', 'dog', 'down', 'the', 'street']]

This makes sense because the entire word list appears in order in the target string.

If we use your original word list ['boy', 'was', 'his', 'dog', 'street', 'the', 'down'], the output would be:

[['boy', 'was', 'his', 'dog', 'street']]

This is the longest consecutive sublist that appears in order in the target.

Key Assumptions #

• Case Insensitivity: We match words regardless of case (e.g., "Boy" and "boy" are considered the same).
• Subsequence, Not Consecutive: The words in the sublist don't need to be consecutive in the target string—they just need to appear in the same order.
• Punctuation Handling: We strip common punctuation from the ends of words to avoid mismatches (e.g., "street." becomes "street").

内容的提问来源于stack exchange，提问作者hockeybro