FastPrepMinimum Dictionary Segments
Problem · String

Minimum Dictionary Segments

Learn this problem
● MediumGoogle logoGoogleFULLTIMEPHONE SCREEN
See Google hiring insights

Problem statement

Given a string s and an array dictionary, split all of s into a sequence of dictionary words.

Return the minimum possible number of words in a complete split. Return -1 if no complete split exists. The empty string requires zero words.

Function

minimumDictionarySegments(s: String, dictionary: String[]) → int

Examples

Example 1

s = "applepie"dictionary = ["apple","app","le","pie"]return = 2

The split apple | pie uses two words. No dictionary word covers the entire string.

Example 2

s = "aaaa"dictionary = ["a","aa","aaa"]return = 2

Either a | aaa or aaa | a uses the minimum of two words.

Example 3

s = "catsandog"dictionary = ["cats","dog","sand","and","cat"]return = -1

Every possible prefix split leaves characters that cannot be covered by a dictionary word.

Constraints

  • 0 <= s.length <= 2000
  • 0 <= dictionary.length <= 2000
  • 1 <= dictionary[i].length <= 50
  • s and every dictionary word contain lowercase English letters.
  • Duplicate dictionary words have no additional effect.

More Google problems

drafts saved locally
public int minimumDictionarySegments(String s, String[] dictionary) {
    // Write your code here.
}
s"applepie"
dictionary["apple","app","le","pie"]
expected2
checking account