NewThe Learning module is now liveSee what's new

You are given a text string text and an array dictionary, where each element in dictionary is a string in the format "<key>:<id>". Here, key represents a token string and id represents its corresponding identifier.

Your task is to implement a function that segments text into a sequence of tokens according to the rules below and returns a list of strings.

The tokenization process must follow these rules:

  • Longest Match Priority: At each position in text, consider all dictionary keys that start at the current index and select the longest possible matching key. If multiple keys match, the longest one must be chosen.
  • Greedy Consumption: Once a token is selected, consume all characters of that token and continue processing from the next unconsumed position in text.

  • Literal Preservation: If no dictionary key matches starting at the current position, the single character at that position must be emitted as a literal token.

  • Output Format: If a segment matches a dictionary key, output its corresponding id. If a segment does not match any dictionary key, output the character itself as a string.

Your implementation should correctly handle all such cases and produce a deterministic token sequence based on the rules above.

Constraints:

  • 11 ≤ text.length ≤ 10910^9
  • 00 ≤ dictionary.length ≤ 10910^9
  • All tokens in dictionary are unique.

Example 1:

Input: text = "applepiepear", dictionary = ["app:10", "apple:20", "pie:30"] Output: ["20", "30", "p", "e", "a", "r"] Explanation: At the start, "apple" is matched instead of the shorter "app". Then "pie" is matched. The remaining characters do not match any token and are kept as literals.

Example 2:

Input: text = "acdebe", dictionary = ["a:1", "b:2", "cd:3"] Output: ["1", "3", "e", "2", "e"]

Example 3:

Input: text = "programmingprogrampropro", dictionary = ["pro:1", "program:2", "programming:3", "gram:4", "ming:5", "pr:6", "og:7"] Output: ["3", "2", "1", "1"]


Accepted
5.2k/16.6k
Acceptance Rate31.3%
Test Cases
Input
text =
dictionary =
Output
Expected