Determine if a string can be segmented

Q: Determine if a string can be segmented

This question evaluates a candidate's understanding of dynamic programming and string-processing skills, along with algorithmic complexity analysis for segmentation problems.

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

Given a string s and a list of strings wordDict, determine whether s can be segmented into a sequence of one or more dictionary words.

You may reuse dictionary words multiple times.
Return true if such a segmentation exists, otherwise return false .

Input

s : a non-empty string
wordDict : a list of non-empty strings

Output

Boolean indicating whether s can be segmented.

Example

s = "leetcode" , wordDict = ["leet", "code"] → true
s = "catsandog" , wordDict = ["cats","dog","sand","and","cat"] → false

Notes / constraints (typical interview assumptions)

1 <= len(s) <= 10^4
1 <= len(wordDict) <= 10^5
Total characters across wordDict can be large; aim for an efficient solution.

Determine if a string can be segmented

Overview

Input

Output

Example

Notes / constraints (typical interview assumptions)

Comments (0)