如何创建满足首尾字符衔接规则的字符串变位词链表

Alright, let's break down how to build this linked list step by step. The core requirements are: each node holds an anagram of a specified string, and each node's last character must match the next node's first character. Let's dive into the implementation with Python (the logic translates easily to other languages too).

1. Generate All Unique Anagrams First #

First off, we need a way to generate every unique anagram of the input string. Using permutations works, but we have to filter out duplicates—especially if the input has repeated characters (like "aab", which would produce duplicate permutations).

from itertools import permutations

def get_unique_anagrams(input_str):
    # Generate all permutations, convert to strings, and deduplicate with a set
    raw_anagrams = permutations(input_str)
    unique_anagrams = set(''.join(perm) for perm in raw_anagrams)
    return list(unique_anagrams)

2. Build a Character-to-Anagrams Map #

To efficiently find anagrams that start with a specific character (the last character of the current node), we'll create a dictionary where keys are starting characters, and values are lists of anagrams that begin with that character. We'll reverse the lists so we can pop elements in O(1) time.

def build_char_anagram_map(anagrams):
    char_map = {}
    for anagram in anagrams:
        first_char = anagram[0]
        if first_char not in char_map:
            char_map[first_char] = []
        char_map[first_char].append(anagram)
    
    # Reverse lists to use pop() for O(1) removals
    for char in char_map:
        char_map[char].reverse()
    return char_map

3. Define the Linked List Node Class #

We'll use a simple node class to represent each element in the linked list:

class ListNode:
    def __init__(self, value=None, next_node=None):
        self.val = value
        self.next = next_node

4. Construct the Linked List #

Now the main logic: we start with any anagram, then repeatedly find an anagram that starts with the current node's last character, link it up, and remove it from our map (to avoid reusing it).

def build_anagram_linked_list(input_str):
    anagrams = get_unique_anagrams(input_str)
    if not anagrams:
        return None  # No valid anagrams (empty input)
    
    char_map = build_char_anagram_map(anagrams)
    
    # Start with the first anagram in our list
    current_anagram = anagrams[0]
    # Remove it from the map
    char_map[current_anagram[0]].pop()
    if not char_map[current_anagram[0]]:
        del char_map[current_anagram[0]]
    
    # Initialize the linked list
    head = ListNode(current_anagram)
    current_node = head
    
    # Keep linking nodes until we've used all anagrams
    while char_map:
        last_char = current_anagram[-1]
        # Check if there are anagrams starting with the last character
        if last_char not in char_map:
            break  # This shouldn't happen if a valid path exists (more on that below)
        
        # Grab the next anagram and update the map
        next_anagram = char_map[last_char].pop()
        if not char_map[last_char]:
            del char_map[last_char]
        
        # Link the new node
        current_node.next = ListNode(next_anagram)
        current_node = current_node.next
        current_anagram = next_anagram
    
    return head

5. A Quick Note on Valid Paths #

You might wonder: will this always work? The answer is yes for non-empty input strings. Here's why:

• Each anagram is a permutation of the input, so the number of anagrams starting with any character c equals the number ending with c (reverse any anagram starting with c to get one ending with c, and vice versa).
• This means we're guaranteed an Eulerian circuit—a path that uses every anagram exactly once and forms a closed loop (or a path that covers all elements if we don't loop back). So our loop should always use all anagrams.

6. Test the Implementation #

Let's test with a sample input to see it in action. We'll also add a helper function to print the linked list:

def print_linked_list(head):
    current = head
    while current:
        print(current.val, end=" -> ")
        current = current.next
    print("None")

# Test with "abc"
input_str = "abc"
linked_list_head = build_anagram_linked_list(input_str)
print_linked_list(linked_list_head)

A possible output:

abc -> cba -> bac -> cab -> bca -> acb -> None

Notice how each node's last character matches the next's first: abc ends with c, cba starts with c; cba ends with a, bac starts with a, and so on.

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