FastPrepCount Word Break Sentences

Count Word Break Sentences

Meta logoMeta● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

Given a lowercase string s and a dictionary wordDict, count the distinct sentences that can be formed by inserting spaces so every resulting word is in the dictionary. The words must cover s in order, without changing or omitting characters. A dictionary word may be reused.

Two sentences are distinct when their word boundaries differ. Return the number of valid sentences, or 0 if no complete segmentation exists. Return only the count; do not construct the sentence strings.

Function

countWordBreakSentences(s: String, wordDict: String[]) → int

Examples

Example 1

s = "catsanddog"wordDict = ["cat","cats","and","sand","dog"]return = 2

There are two segmentations: cats and dog and cat sand dog.

Example 2

s = "pineapplepenapple"wordDict = ["apple","pen","applepen","pine","pineapple"]return = 3

The three word-boundary choices form three valid sentences, including one that reuses apple.

Example 3

s = "catsandog"wordDict = ["cats","dog","sand","and","cat"]return = 0

No sequence of dictionary words covers every character.

Constraints

  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • s and every dictionary word contain only lowercase English letters.
  • Dictionary words are unique.
  • The number of valid sentences does not exceed 100000.

More Meta problems

See Meta hiring insights
public int countWordBreakSentences(String s, String[] wordDict) {
    // Write your code here
}
s"catsanddog"
wordDict["cat","cats","and","sand","dog"]
expected2
Checking account…