Determine dictionary-based string segmentation

Q: Determine dictionary-based string segmentation

This question evaluates string segmentation competency, including understanding of dynamic programming, scalable token-matching techniques (prefix data structures and hashing), and handling large input sizes.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given a string s and a set of tokens dict. Determine whether s can be segmented into a sequence of one or more tokens from dict. If segmentation is possible, return one valid segmentation; otherwise return an empty result. Discuss and implement an approach that scales to |s| up to 1e5 and |dict| up to 1e5 (consider prefix pruning via tries or hashing, and dynamic programming with early exits). Analyze time and space complexity, and explain how you would extend the solution to count the number of distinct segmentations modulo 1,000,000,007.

Determine dictionary-based string segmentation

Overview

Comments (0)