Word Break II Problem

Word Break II Problem — ExecCode Hard DSA Practice

Solve the Word Break II problem on ExecCode. Free online hard DSA practice in Trie. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Description Imagine you're solving Word Break II in a real system where you must be correct and efficient. Problem Given a non-empty string s and a list of non-empty words wordDict, find all possible sentences where s can be segmented into a sequence of one or more dictionary words. A sentence is a sequence of dictionary words joined by single spaces that concatenates to s exactly. Return all such sentences in any order. Each word from the dictionary may be used multiple times. Input Format The program receives two values on standard input separated by a newline: the first line is the string s; the second line is the comma-separated list of words in wordDict (no extra spaces around words). Output Format Print each valid sentence on its own line. The order of lines does not matter. Constraints All inputs are lowercase letters only. 1 <= length of s <= 30 (for these tests). 1 <= number of words in wordDict <= 20. You must preserve the meaning: generate all sentences that exactly concatenate to s using words from wordDict, separated by single spaces.

Examples

Input raw = "catsanddog\ncat,cats,and,sand,dog"; Output "cat sand dog\ncats and dog". Input raw = "pineapplepenapple\npine,apple,pen,applepen,pineapple"; Output "pine apple pen apple\npine applepen apple\npineapple pen apple"

Constraints

1 <= len(s) <= 20

Practice Word Break II free on ExecCode. Browse DSA problems, topic map, and placement guides.