Solve Nearby Inventory and Word Segmentation Tasks

Two Algorithmic Tasks

Implement both parts. They are independent and should have separate functions.

Part A - Nearby Centers with Inventory

An undirected graph represents delivery routes between centers. Given connections, a destination, a nonnegative max_step, and an inventory map, return every center that can send inventory to the destination.

Implement:

eligible_centers(connections, destination, max_step, inventory) -> list[int]

A center is eligible when all of the following hold:

• It is not the destination.
• Its inventory value is greater than zero.
• Its shortest-path distance to the destination is at most max_step.

The result may be returned in any order. Centers may appear in inventory even if they have no route, and routes may mention centers absent from inventory; a missing inventory value means zero.

Example:

connections = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]]
destination = 4
max_step = 1
inventory = {1: 2, 2: 0, 3: 5, 4: 3, 5: 6}

result = [3, 5]

Constraints:

• 0 <= len(connections) <= 100000
• Center IDs are integers.
• Duplicate edges and self-loops may appear and must not change the result.

Hints:

• Search outward from the destination rather than running a search from every stocked center.
• Once the search reaches max_step, deeper nodes are irrelevant.

Part B - Return One Word Segmentation

Given a lowercase string and a dictionary, return any sequence of dictionary words whose concatenation is exactly the string.

Implement:

segment_words(text, dictionary) -> list[str]

You may treat membership in dictionary as the reported isWord helper. At least one valid segmentation is guaranteed. Do not reorder or omit characters.

Example:

text = "myhousehavecat"
dictionary = {"my", "house", "have", "cat", "househave"}

result = ["my", "house", "have", "cat"]

Returning ["my", "househave", "cat"] is also valid.

Constraints:

• 1 <= len(text) <= 2000
• Every dictionary word is nonempty and lowercase.
• The dictionary contains at most 20000 words.

Hints:

• Backtrack from a character index and try valid next words.
• Cache indices that cannot lead to a complete segmentation so repeated suffixes are not recomputed.
• Bounding candidate lengths by the longest dictionary word can reduce unnecessary checks.

Discussion Extensions

• Give the time and space complexity of each part.
• How would Part B change if all valid segmentations were required?
• How would you make Part A answer many destination queries on a mostly static graph?