Determine if a string can be segmented

Q: Determine if a string can be segmented

This is a Coding & Algorithms interview question from ByteDance for Machine Learning Engineer roles. View the full question and solution on PracHub.

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

Input

Output

Example

Notes / constraints (typical interview assumptions)

Comments (0)